Dual d'un polyèdre | EPFL Graph Search

En géométrie, il existe plusieurs façons (géométrique, combinatoire) de mettre les polyèdres en dualité : on peut se passer de support géométrique et définir une notion de dualité en termes purement combinatoires, qui s'étend d'ailleurs aux polyèdres et polytopes abstraits. Dans chaque cas, à tout polyèdre est associé un polyèdre appelé dual du premier, tel que :

le dual du polyèdre dual est le polyèdre initial,
les faces de l'un sont en correspondance avec les sommets de l'autre, en respectant les propriétés d'adjacence.

L'exemple le plus simple de dualité s'obtient pour les polyèdres réguliers convexes en reliant les centres des faces adjacentes (voir § Dualité des solides de Platon). On peut aussi utiliser la construction dite de Dorman Luke indiquée plus loin. Plus généralement, on définit une dualité en considérant l'opération de conjugaison par rapport à la sphère circonscrite. Quelques propriétés *Le dual d'un polyèdre convexe est aussi un polyèdre convexe. :L

On canonical representation of convex polyhedra

Stefano Picozzi

Convex polyhedra are important objects in various areas of mathematics and other disciplines. A fundamental result, known as Minkowski-Weyl theorem, states that every polyhedron admits two types of representations, either as the solution set to a finite system of linear inequalities or the Minkowski sum of a finite set of points and half-rays. These are usually referred to as its H-representations and its V-representations, respectively. Neither H-representations nor V-representations are unique. Hence, deciding whether two H-representations, or two V-representations describe the same polyhedron is a nontrivial problem. We identify particular representations which are easy to determine, are compact, and reflect the geometrical properties of the underlying polyhedron. Key ingredients to this discussion are affine transformations of polyhedra, duality and complexity of polyhedral decision problems. In this dissertation, we discuss in detail the problem of refining the definitions of Hand V- representations such as to guarantee a one to one correspondence between polyhedra and their representations. As a convenient formalism, we introduce the notion of the canonical representation rule, which is any function assigning to each polyhedron P a particular H-representation, and a particular V-representation. The orthogonal representation rule is a well-known example of such a function. We define the lexico-smallest representation rule, an improved canonical representation rule that produce representations which are nonredundant, make the underlying geometry transparent and, furthermore, are sparse. These rules also exhibit nice polarity properties that can be exploited for computation. The key computational tool is linear programing. Furthermore, we show that the lexico-smallest H-representation of a perfect bipartite matching polyhedron is easy to determine using the combinatorial properties of the underlying graph. Finally, we discuss the complexity of various polyhedral verification problems related to representation of convex polyhedra. The standard technique to identify the redundancies within an H- or a V-representation is to use linear programming. We discuss the complexity of the converse reduction. More precisely, we show that deciding the feasibility of a system of linear inequalities can be reduced to deciding redundancy in an H- or in a V- representation in linear time. Also, we will study the equivalence of these problems with those of identifying the implicit linearities within an H- or a V- representation, and the boundedness of a polyhedron.

EPFL2005

The lexico-smallest representation of convex polyhedra

Stefano Picozzi

Every convex polyhedron in the Euclidean space

R^d

admits both H- and V-representation. For both formats, a representation is canonical if it is minimal and unique up to some elementary operations. In this paper, we extend the usual definition of canonical representation to a family of such representations that can be computed in polynomial time. In particular, this allows to define the lexico-smallest representation which computation is easy in practice. Furthermore, it guarantees certain sparsity property reflecting the real dimension of the studied object. As a consequence, H-representations of non-full dimensional polyhedra and V-representations of polyhedra without extreme points can be compared more efficiently.

2003

On duality of canonical representations

Stefano Picozzi

Every convex polyhedron in

R^d

admits both H- and V-representations. In both cases, a representation is defined to be canonical if it is minimal and unique up to simple transformations. In general, canonical H- and V-representations are discussed separately, resulting in two different definitions. In contrast, the duality of polyhedral cones suggests a possible "unification" of the two types of canonical representations. In this paper, we describe a family of canonical representations, the dfnS-canonical representations, which definitions are the same for both H- and V-representation. We show that every S-canonical V-representation coincide with the S-canonical H-representation of a certain polyhedron. As a consequence, methods developed to determine S-canonical H-representations can be applied successfully in V-representation.

2004

The lexico-smallest representation of convex polyhedra

Stefano Picozzi

Every convex polyhedron in the Euclidean space

R^d

2003

On duality of canonical representations

Stefano Picozzi

Every convex polyhedron in

R^d

2004

On canonical representation of convex polyhedra

Stefano Picozzi

EPFL2005