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]

${\displaystyle 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. The inverse (dual) problem of finding the bounding inequalities given the vertices is called facet enumeration (see convex hull algorithms).

Computational complexity

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(n²dv) time and O(nd) space complexity. The Avis–Fukuda algorithm adapted the criss-cross algorithm for oriented matroids.

A recent study by Dong, Fan, Xiong, and Zeng ^[4] enhanced vertex enumeration for hyperplane arrangements by introducing the Zero rule into an optimized reverse-search algorithm. This novel, objective-free pivoting 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(n²d²(v-v_d) + ndv_d) where v_d denotes the number of dictionaries that reach the terminal state in exactly d pivots under the Zero rule. This becomes O(nd⁴v) for simple arrangements, substantially improving upon the O(n²dv) complexity of its predecessor. Empirical studies confirm its superior performance on arrangements with numerous hyperplanes.

Notes

1. Eric W. Weisstein CRC Concise Encyclopedia of Mathematics, 2002, ISBN   1-58488-347-2, p. 3154, article "vertex enumeration"
2. 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 .
3. 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 .
4. Zelin Dong; Fenglei Fan; Huan Xiong; Tieyong Zeng (March 2025). "An Efficient Algorithm for Vertex Enumeration of Arrangement". Arxiv . 2. arXiv: 2401.16675 .

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.

• Zelin Dong; Fenglei Fan; Huan Xiong; Tieyong Zeng (March 2025). "An Efficient Algorithm for Vertex Enumeration of Arrangement". Arxiv . 2. arXiv: 2401.16675 .