Dual polyhedron | EPFL Graph Search

In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all can also be constructed as geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron. Duality preserves the symmetries of a polyhedron. Therefore, for many classes of polyhedra defined by their symmetries, the duals belong to a corresponding symmetry class. For example, the regular polyhedra – the (convex) Platonic solids and (star) Kepler–Poinsot polyhedra – form dual pairs, where the regular tetrahedron is self-dual. The dual of an isogonal polyhedron (one in which any two vertices are equivalent under symmetries of the polyhedron) is an isohedral polyhedron (one in which any two faces are equivalen

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

On canonical representation of convex polyhedra

Stefano Picozzi

EPFL2005

On duality of canonical representations

Stefano Picozzi

Every convex polyhedron in

R^d

2004

The lexico-smallest representation of convex polyhedra

Stefano Picozzi

Every convex polyhedron in the Euclidean space

R^d

2003