Vertex enumeration problem: Difference between revisions

Revision as of 11:21, 3 October 2008

Latest revision as of 18:49, 6 August 2022

(32 intermediate revisions by 21 users not shown)

Line 1:

TheIn mathematics, the '''vertex enumeration problem''' for a [[polyhedronpolytope]], 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 polyhedronpolytope]] specified by a [[set of linear inequalities]]:<ref>[[Eric W. Weisstein]] ''CRC Concise Encyclopedia of MathematicMathematics,'' 2002,ISBN 1584883472{{isbn|1-58488-347-2}}, p. &nbsp;3154, article "vertex enumeration"</ref>

:<math>Ax \leq b</math>

where ''A'' is an ''m''&times;×''n'' matrix, ''x'' is an ''n''&times;1×1 column vector of variables, and ''b'' is an ''m''&times;1×1 column vector of constants. The inverse ([[Duality (mathematics)|dual]]) problem of finding the bounding inequalities given the vertices is called ''[[facet enumeration]]'' (see [[convex hull algorithms]]).

==Computational complexity==

The [[Computational complexity theory|computational complexity]] of the problem is a subject of research in [[computer 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.<ref>{{cite journal|author1=Leonid Khachiyan |author2=Endre Boros |author3=Konrad Borys |author4=Khaled Elbassioni |author5=Vladimir Gurvich |title=Generating All Vertices of a Polyhedron Is Hard |journal=[[Discrete and Computational Geometry]] |volume=39 |number=1–3 |date=March 2008 |pages=174–190 |doi= 10.1007/s00454-008-9050-5|doi-access=free }}</ref>

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

A 1992 article by D.[[David Avis]] and K.[[Komei Fukuda]]<ref>[http://www.springerlink.com/content/m7440v7p3440757u/{{cite journal|author1=David Avis and |author2=Komei Fukuda, "|title=A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra"], ''|journal=[[Discrete and Computational Geometry]]'', Volume |volume=8, Number |number=1 / |date=December, 1992, 295-313,|pages=295–313 {{doi|doi=10.1007/BF02293050|doi-access=free }}</ref> presents thea [[reverse-search algorithm]] which finds the ''v'' vertices of a polyhedronpolytope 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]] O(''nd''). 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. The Avis–Fukuda algorithm adapted the [[criss-cross algorithm]] for oriented matroids.

==ReferencesNotes==

{{reflist}}

==References==

[[Category:Polyhedra]]

* {{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}}

[[Category:Geometric algorithms]]

[[Category:Linear programming]]

[[Category:Polyhedral combinatorics]]

[[Category:Polyhedra]]

[[Category:Discrete geometry]]

[[Category:Enumerative combinatorics]]

[[Category:Mathematical problems]]

[[Category:Computational geometry]]