PRIMAL-DUAL METHODS FOR VERTEX AND FACET ENUMERATION

Every convex polytope can be represented as the intersection of a fini te set of halfspaces and as the convex hull of its vertices. Transform ing from the halfspace (resp. vertex) to the vertex (resp. halfspace) representation is called vertex enumeration (resp. facet enumeration). An open question is whether there is an algorithm for these two probl ems (equivalent by geometric duality) that is polynomial in the input size and the output size. In this paper we extend the known polynomial ly solvable classes of polytopes by looking at the dual problems. The dual problem of a vertex (resp. facet) enumeration problem is the face t (resp. vertex) enumeration problem for the same polytope where the i nput and output are simply interchanged. For a particular class of pol ytopes and a fixed algorithm, one transformation may be much easier th an its dual. In this paper we propose a new class of algorithms that t ake advantage of this phenomenon. Loosely speaking, primal-dual algori thms use a solution to the easy direction as an oracle to help solve t he seemingly hard direction.