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:
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 problem of finding the bounding inequalities given the vertices is called facet enumeration.
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.A 1992 article by David Avis and Komei Fukuda presents a reverse-search algorithm which finds the v vertices of a polytope defined by a nondegenerate system of n inequalities in d dimensions in time O and space O. The v vertices in a simple arrangement of n hyperplanes in d dimensions can be found in O time and O 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 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 where vd denotes the number of dictionaries that reach the terminal state in exactly d pivots under the Zero rule. This becomes O for simple arrangements, improving upon the O complexity of its predecessor.