A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra

Abstract

We present a new pivot-based algorithm which can be used with minor modification for the enumeration of the facets of the convex hull of a set of points, or for the enumeration of the vertices of an arrartgement or of a convex polyhedron, in arbitrary dimension. The algorithm has the following properties: (a) No additional storage is required beyond the input dam, (b) The output list produced is frw of duplicates; (c) The algorithm is extremely simple, requires no data structures, and handles all degenerate cases; (d) The running time is output sensitive for nondegenerate inputs; (e) The algorithm is easy to efficiently paraIIeIize. For example, the algorithm finds the v vertices of a polyhedron in R d defined by a non-degenerate system of n inequalities (or dually, the v facets of the convex hull of n points in R ~, where each facet contains exactly d given points) in time O (ndv ) and O (rid) space. The v vertices in a simple arrangement of n hyperplanes in R d can be found in O (n2dv ) time and O (rid) space complexity. The algorithm is based on inverting finite pivot algorithms for linear programming.