Content deleted Content added
←Created page with 'The '''vertex enumeration problem''' for a polyhedron, a polyhedral cell complex, a hyperplane arrangement, or some other object of [[discrete geometry...' |
mNo edit summary |
||
Line 1:
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 [[vertex (geometry)|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 D. Avis and K. 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
==References==
| |||