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 In mathematics, and specifically in topology, a CW complex (also cellular complex or cell complex) is a topological space that is built by gluing together topological balls (so-called ''cells'') of different dimensions in specific ways. It generali ...

, 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 geom ...

, 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 A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

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 Convex hull#Applications, broad range of applications in mathematics and computer science. In computational geometry, numerous algorithms are proposed for computing the convex hull o ...

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, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied 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 (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 In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...

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

space Space is a three-dimensional continuum containing positions and directions. In classical physics, physical space is often conceived in three linear dimensions. Modern physicists usually consider it, with time, to be part of a boundless ...

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

hyperplane In geometry, a hyperplane is a generalization of a two-dimensional plane in three-dimensional space to mathematical spaces of arbitrary dimension. Like a plane in space, a hyperplane is a flat hypersurface, a subspace whose dimension is ...

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 In optimization (mathematics), 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 programming, linear ...

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