A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
David Avis, Komei Fukuda · 1991
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.