Vertex enumeration problem
In mathematics, the vertex enumeration problem for a polyhedron, 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 polyhedron specified by a set of linear inequalities:[1]
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 D. Avis and K. Fukuda[2] presents the algorithm which finds the v vertices of a polyhedron 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 O(nd) space. The v vertices in a simple arrangement of n hyperplanes in d dimensions can be found in O(n2dv) time and O(nd) space complexity.
References
- ^ Eric W. Weisstein CRC Concise Encyclopedia of Mathematic, 2002,ISBN 1584883472, p. 3154, article "vertex enumeration"
- ^ David Avis and Komei Fukuda, "A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra", Discrete and Computational Geometry, Volume 8, Number 1 / December, 1992, 295-313, doi:10.1007/BF02293050