Vertex enumeration problem: Difference between revisions

Revision as of 00:35, 24 January 2009

Revision as of 13:25, 24 January 2009

Line 7:

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 thean algorithm which finds the ''v'' vertices of a polyhedron defined by a nondegenerate system of ''n'' inequalities in ''d'' dimensions (or, dually, the ''v'' [[facet]]s 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'' [[hyperplane]]s in ''d'' dimensions can be found in O(''n''²''dv'') time and O(''nd'') space complexity.

==References==