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]
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. The inverse (dual) problem of finding the bounding inequalities given the vertices is called facet enumeration (see convex hull algorithms).
Computational complexity
[edit]The computational complexity of the problem is a subject of research in computer science. For unbounded polyhedra, the problem is known to be NP-hard, more precisely, there is no algorithm that runs in polynomial time in the combined input-output size, unless P=NP.[2]
A 1992 article by David Avis and Komei Fukuda[3] presents a reverse-search 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(n2dv) time and O(nd) space complexity. The Avis–Fukuda algorithm adapted the criss-cross algorithm for oriented matroids.
A 2025 article by Zelin Dong, Fenglei Fan, Huan Xiong, and Tieyong Zeng[4] introduced the Zero rule into an optimized reverse-search algorithm. This pivot rule is proven to terminate within d steps. Through a formal analysis of its properties, the rule was integrated into an efficient algorithm, achieving a time complexity O(n2d2(v-vd) + ndvd) where vd denotes the number of dictionaries that reach the terminal state in exactly d pivots under the Zero rule. This becomes O(nd4v) for simple arrangements, improving upon the O(n2dv) complexity of its predecessor.
Notes
[edit]- ^ Eric W. Weisstein CRC Concise Encyclopedia of Mathematics, 2002, ISBN 1-58488-347-2, p. 3154, article "vertex enumeration"
- ^ Leonid Khachiyan; Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich (March 2008). "Generating All Vertices of a Polyhedron Is Hard". Discrete and Computational Geometry. 39 (1–3): 174–190. doi:10.1007/s00454-008-9050-5.
- ^ 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.
- ^ Zelin Dong; Fenglei Fan; Huan Xiong; Tieyong Zeng (March 2025). "An Efficient Algorithm for Vertex Enumeration of Arrangement". Arxiv. 2. arXiv:2401.16675.
References
[edit]- 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.
- Zelin Dong; Fenglei Fan; Huan Xiong; Tieyong Zeng (March 2025). "An Efficient Algorithm for Vertex Enumeration of Arrangement". Arxiv. 2. arXiv:2401.16675.