Convex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts[1][2] use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others[3] (including this article) allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.
Convex polytopes play an important role both in various branches of mathematics and in applied areas, most notably in linear programming.
In the influential textbooks of Grünbaum[1] and Ziegler[2] on the subject, as well as in many other texts in discrete geometry, convex polytopes are often simply called "polytopes". Grünbaum points out that this is solely to avoid the endless repetition of the word "convex", and that the discussion should throughout be understood as applying only to the convex variety (p. 51).
A polytope is called full-dimensional if it is an -dimensional object in .
Algorithmic problems for a convex polytope[edit]
Construction of representations[edit]
Different representations of a convex polytope have different utility, therefore the construction of one representation given another one is an important problem. The problem of the construction of a V-representation is known as the vertex enumeration problem and the problem of the construction of a H-representation is known as the facet enumeration problem. While the vertex set of a bounded convex polytope uniquely defines it, in various applications it is important to know more about the combinatorial structure of the polytope, i.e., about its face lattice. 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. edges) around the convex hull. It is a trivial task when the convex polygon is specified in a traditional way for polygons, i.e., by the ordered sequence of its vertices . 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.[14]
Volume computation[edit]
The task of computing the volume of a convex polytope has been studied in the field of computational geometry. The volume can be computed approximately, for instance, using the convex volume approximation technique, when having access to a membership oracle. As for exact computation, one obstacle is that, when given a representation of the convex polytope as an equation system of linear inequalities, the volume of the polytope may have a bit-length which is not polynomial in this representation.[15]