Go up to 2 Coordinate Descriptions
Go forward to 2 Facet Enumeration

## 1 Vertex Enumeration

Input: Polytope P in H-description Non-redundant V-description of P
Status (general): Open; polynomial total time if P is simple or simplicial 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.