On the complexity of vertex and facet enumeration for convex polytopes
David M. Avis, David Avis · 1998
Every convex polytope is both the intersection of a finite set of halfspaces and the convex hull of a finite vertex set. Transforming from the halfspaces (vertices, respectively) to the vertices (halfspaces, respectively) is called vertex enumeration (facet enumeration, respectively). It is an open problem whether there is an algorithm for these two problems polynomial in the input and the output size. For each of the known methods, this thesis develops a characterization of what constitutes an easy or difficult input. Example families of polytopes are presented that show that none of the known methods will yield a polynomial algorithm. On the other hand, a family of polytopes difficult for one class of algorithms can (sometimes) be easily solvable for another class of algorithms; the characterizations given here can be used to guide a choice of algorithms. Similarly, although the general problems of vertex and facet enumeration are equivalent by the duality of convex polytopes, for fixed polytope family and algorithm, one of these directions can be much easier than the other. This thesis presents a new class of algorithms that use the easy direction as an oracle to solve the seemingly difficult direction.