A classic theorem from convexity is that every polytope P can be expressed as the convex hull of its n extreme points (or vertices) V. These descriptions of P will be referred to as the halfspace and vertex descriptions, respectively. The size of a polytope, denoted size (P) = (nz+n)d, is the spacerequired to store both descriptions of a polytope. Each vertex of P lies on d affinely independent hyperplanes each of which bounds a halfspace in %. The set of indices of such a set of halfspaces is called a basis. A polytope is simple if each of its vertices has a unique basis. There are three closely related computational problems concerning the two descriptions of a polytope: q The vertex enumeration problem is to compute V from W, q The convex hull problem it to compute %! from V. q The polyfope verijlcation problem is to decide whether a given vertex description and halfspace description define the same polytope. It is an open problem whether any of these problems can be solved in time polynomial in size (P). Since the first two problems are essentially equivalent under point/hyperplane duality, we will mainly restrict ourself to the vertex enumeration problem, although all results apply to both problems. There are two main classesof algorithms for solving these problems: pivoting algorithms and insertion algorithms. A pivoting algorithm for the vertex enumeration problem begins by finding a basis of some vertex of P. Two bases of P are adjacent if they differ in one index only. This adjacency relation defines a graph on the bases of P, where each edge corresponds to a pivot, the replacement of exactly one index in a basis. All vertices of this graph are generated, from which the extreme points of P are readily computed. Representatives brenmer@cs.mcgill.ca Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association of Computing Machinery,To copy otherwise, or to republish, requires a fee and/or specific permission. and polytope verification problems (and by duality the convex hull problem for simplicial polytopes) in time polynomial in size(P). For non-simple polytopes the number of bases maybe exponential in the size of P. For such polytopes pivoting algorithms rely on perturbation, either symbolic or numerical, to reduce the computation time. In Section 3 we give a fairly general model for pivoting algorithms and valid perturbation schemes for polytopes. We then give examples of polytopes for which no valid perturbation scheme can yield polynomial time pivoting algorithms in this model. However, it is well-known that size (P) E Q(rnd) and this bound is also achieved. An efficient vertex enumeration algorithm for such polytopes should clearly be polynomial in md. It is not known whether such an algorithm exists. Examples that have arisen in practice (see e.g. [5]) suggest that the sizes of polytopes of interest are closer to the lower bound than the upper. Since there is such a wide variation in the output sizes of vertex enumeration problems, we suggest size(P) as the appropriate measure of the problem size. The success of insertion algorithms is widely believed to depend on keeping the vertex complexity of the intermediate polytopes generated small by judicious choice of the order in which the halfspaces are inserted. While this is necessary for the success of such algorithms, it is not sufficient. The examples in Section 3 show that insertion algorithms which rely on triangulation (such as the the randomized and derandomized algorithms) can perform very badly indeed, even when the intermediate polytopes have small size and regardless of the order of insertion of the halfspaces. For insertion algorithms that do not rely on triangulation, the choice of insertion order is indeed a critical factor. Dyer [10] uses a result of Klee [14] to give a family of polytopes for which there is an order of halfspace insertion that causes any insertion algorithm to build exponential sized intermediate polytopes. Dyer's 1lth Computational Geometry, Vancouver, B.C. Canada
Nevertheless, the complexity of the double description method may be exponential in the size of the input and the output (see REF which shows how to build "bad" candidates).
How good are convex hull algorithms?
SCG '95
Computer Science