The Complexity of Vertex Enumeration Methods

Abstract

The computational complexity of problems relating to the enumeration of all the vertices of a convex polyhedron defined by linear inequalities is examined. Several published approaches are evaluated in this light. A new algorithm is described, and shown to have a better complexity estimate than existing methods. Empirical evidence supporting the theoretical superiority is presented. Finally vertex enumeration is discussed when the space containing the polyhedra is of fixed dimension and only the size of the inequality system is permitted to vary.