|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 ). 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  found an O(më d/2û ) polynomial time algorithm, which is optimal by the Upper Bound Theorem of McMullen . 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 .
For general d, the reverse search method of Avis and Fukuda  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  solves the problem for simplicial polytopes. Note that these algorithms need a vertex of P to start from. Provan  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 . Most of these algorithms can be generalized to directly work for unbounded polyhedra, too.
|Related problems:||2, 3, 5, 7|