A Day On Wikipedia

The ”’vertex enumeration problem”’ for a [[polyhedron]], 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 polyhedron]] specified by the set of linear inequalities:<ref>[[Eric W. Weisstein]] ”CRC Concise Encyclopedia of Mathematic,” 2002,ISBN 1584883472, p. 3154, article ‘vertex enumeration'</ref>

==Computational complexity==
The [[computational complexity]] of the problem is a subject of research in [[computer science]].

A 1992 article by Avis and Fukuda <ref>[http://www.springerlink.com/content/m7440v7p3440757u/ David Avis and Komei Fukuda, ‘A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra’], ”[[Discrete and Computational Geometry]]”, Volume 8, Number 1 / December, 1992, 295-313, {{doi|10.1007/BF02293050}}</ref> presents the algorithm which finds the v vertices of a polyhedron 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 [[Big Oh notation|O]](ndv) and O(nd) [[space complexity|space]]. 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.

==References==
{{reflist}}

[[Category:Polyhedra]]
[[Category:Geometric algorithms]]
[[Category:Discrete geometry]]