Convex polytope
Convex polytopes play an important role both in various branches of mathematics and in applied areas, most notably in linear programming.
A convex polytope may be defined in a number of ways, depending on what is more suitable for the problem at hand.
Grünbaum's definition is in terms of a convex set of points in space.
A convex polytope may be defined as an intersection of a finite number of half-spaces.
However, for a full-dimensional convex polytope, the minimal H-description is in fact unique and is given by the set of the facet-defining halfspaces.
Hence, a closed convex polytope may be regarded as the set of solutions to the system of linear inequalities: where
An open convex polytope is defined in the same way, with strict inequalities used in the formulas instead of the non-strict ones.
In this case, there is a unique minimal set of defining inequalities (up to multiplication by a positive number).
Inequalities belonging to this unique minimal system are called essential.
The set of points of a polytope which satisfy an essential inequality with equality is called a facet.
Therefore, in general there is no unique minimal set of inequalities defining the polytope.
However if one wishes to have a definition equivalent to that as a convex hull, then bounding must be explicitly required.
By requiring that the intersection of half-spaces results in a bounded set, the definition becomes equivalent to the vertex-representation.
We consider the intersection of all the corresponding hyperplanes (which divide the space into the half-spaces) that contain
For an unbounded polytope (sometimes called: polyhedron), the H-description is still valid, but the V-description should be extended.
[6] In other words, every vector in an unbounded polytope is a convex sum of its vertices (its "defining points"), plus a conical sum of the Euclidean vectors of its infinite edges (its "defining rays").
Equivalently, a face is the set of points giving equality in some valid inequality of the polytope.
Each point on a given facet will satisfy the linear equality of the corresponding row in the matrix.
By a result of Whitney[7] the face lattice of a three-dimensional polytope is determined by its graph.
The same is true for simple polytopes of arbitrary dimension (Blind & Mani-Levitska 1987, proving a conjecture of Micha Perles).
[8] Kalai (1988)[9] gives a simple proof based on unique sink orientations.
Because these polytopes' face lattices are determined by their graphs, the problem of deciding whether two three-dimensional or simple convex polytopes are combinatorially isomorphic can be formulated equivalently as a special case of the graph isomorphism problem.
However, it is also possible to translate these problems in the opposite direction, showing that polytope isomorphism testing is graph-isomorphism complete.
A convex polytope can be decomposed into a simplicial complex, or union of simplices, satisfying certain properties.
Given a convex r-dimensional polytope P, a subset of its vertices containing (r+1) affinely independent points defines an r-simplex.
Every regular convex polyhedron (Platonic solid) can be dissected into some even number of instances of its characteristic orthoscheme.
Various convex hull algorithms deal both with the facet enumeration and face lattice construction.
In the planar case, i.e., for a convex polygon, both facet and vertex enumeration problems amount to the ordering vertices (resp.
When the input list of vertices (or edges) is unordered, the time complexity of the problems becomes O(m log m).
[13] A matching lower bound is known in the algebraic decision tree model of computation.
