In mathematics, the vertex enumeration problem for a

polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...

, a polyhedral

cell complex A CW complex (also called cellular complex or cell complex) is a kind of a topological space that is particularly important in algebraic topology. It was introduced by J. H. C. Whitehead (open access) to meet the needs of homotopy theory. This clas ...

, a

hyperplane arrangement In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set ''A'' of hyperplanes in a linear, affine, or projective space ''S''. Questions about a hyperplane arrangement ''A'' generally concern geometrical, ...

, or some other object of

discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic ge ...

, 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: :

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 Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science. In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of poin ...

Computational complexity

The computational complexity of the problem is a subject of research in

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...

. 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 (or, dually, the ''v''

facet Facets () are flat faces on geometric shapes. The organization of naturally occurring facets was key to early developments in crystallography, since they reflect the underlying symmetry of the crystal structure. Gemstones commonly have facets cut ...

s of the convex hull of ''n'' points in ''d'' dimensions, where each facet contains exactly ''d'' given points) in time O(''ndv'') and

space Space is the boundless three-dimensional extent in which objects and events have relative position and direction. In classical physics, physical space is often conceived in three linear dimensions, although modern physicists usually cons ...

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 In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear object ...

for oriented matroids.

Notes

References

* {{cite journal, first1=David, last1=Avis, first2=Komei, last2=Fukuda, authorlink2=Komei Fukuda, authorlink1=David Avis, title=A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, journal=

Discrete and Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geome ...

, volume=8, number=1, date=December 1992, pages=295–313 , doi=10.1007/BF02293050, mr=1174359, doi-access=free Geometric algorithms Linear programming Polyhedral combinatorics Polyhedra Discrete geometry Enumerative combinatorics Mathematical problems Computational geometry