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 cla ...

, a hyperplane arrangement, 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 In mathematics a linear inequality is an inequality which involves a linear function. A linear inequality contains one of the symbols of inequality:. It shows the data which is not equal in graph form. * greater than * ≤ less than or equal to ...

: :

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 In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

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 (includin ...

. 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 David Michael Avis (born March 20, 1951) is a Canadian and British computer scientist known for his contributions to geometric computations. Avis is a professor in computational geometry and applied mathematics in the School of Computer Scienc ...

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 cu ...

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 con ...

O(''nd''). The ''v'' vertices in a simple arrangement of ''n''

hyperplane In geometry, a hyperplane is a subspace whose dimension is one less than that of its '' ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hype ...

s 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.

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 ge ...

, 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