Vertex enumeration problem

In mathematics, the vertex enumeration problem for a polytope, a polyhedral cell complex, a hyperplane arrangement, or some other object of discrete geometry, is the problem of determination of the object's vertices given some formal representation of the object. A classical example is the problem of enumeration of the vertices of a convex polytope specified by a set of linear inequalities:^[1]

$Ax \leq b$

where A is an m×n matrix, x is an n×1 column vector of variables, and b is an m×1 column vector of constants.

Computational complexity

The computational complexity of the problem is a subject of research in computer science.

A 1992 article by David Avis and Komei Fukuda^[2] presents an algorithm which finds the v vertices of a polytope defined by a nondegenerate system of n inequalities in d dimensions (or, dually, the v facets of the convex hull of n points in d dimensions, where each facet contains exactly d given points) in time O(ndv) and space O(nd). The v vertices in a simple arrangement of n hyperplanes in d dimensions can be found in O(n²dv) time and O(nd) space complexity. The Avis–Fukuda algorithm adapted the criss-cross algorithm for oriented matroids.

Notes

1. Eric W. Weisstein CRC Concise Encyclopedia of Mathematics, 2002, ISBN 1-58488-347-2, p. 3154, article "vertex enumeration"
2. David Avis; Komei Fukuda (December 1992). "A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra". Discrete and Computational Geometry 8 (1): 295–313. doi:10.1007/BF02293050.

References

• Avis, David; Fukuda, Komei (December 1992). "A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra". Discrete and Computational Geometry 8 (1): 295–313. doi:10.1007/BF02293050. MR 1174359.