| Input: | Polytope P in H-description |
|---|---|
| Output: | Non-redundant V-description of P |
| Status (general): | Open; polynomial total time if P is simple or simplicial |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
Let d = dim(P) and let m be the number of inequalities in the
input. It is well known that the number of vertices n can be
exponential (W(më d/2û )) in the size of
the input (e.g., Cartesian products of suitably chosen
two-dimensional polytopes and prisms over them).
VERTEX ENUMERATION is strongly polynomially equivalent to Problem 3 (see Avis, Bremner, and Seidel [1]). Since Problem 2 is strongly polynomially equivalent to Problem 3 as well, VERTEX ENUMERATION is also strongly polynomially equivalent to Problem 2. For fixed d, Chazelle [12] found an O(më d/2û ) polynomial time algorithm, which is optimal by the Upper Bound Theorem of McMullen [43]. There exist algorithms which are faster than Chazelle's algorithm for small n, e.g., an O(m log n + (m n)1-1/(ë d/2û +1) polylog m) algorithm of Chan [9]. For general d, the reverse search method of Avis and Fukuda [2] solves the problem for simple polyhedra in polynomial total time, using working space (without space for output) bounded polynomially in the input size. An algorithm of Bremner, Fukuda, and Marzetta [8] solves the problem for simplicial polytopes. Note that these algorithms need a vertex of P to start from. Provan [54] gives a polynomial total time algorithm for enumerating the vertices of polyhedra arising from networks. There are many more algorithms known for this problem - none of them is a polynomial total time algorithm for general polytopes. See the overview article of Seidel [59]. Most of these algorithms can be generalized to directly work for unbounded polyhedra, too. |
| Related problems: | 2, 3, 5, 7 |
|---|