Vertex enumeration problem: Difference between revisions

Revision as of 08:23, 19 November 2017

Revision as of 03:56, 7 February 2019

Line 5:

==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|url=https://link.springer.com/article/10.1007/s00454-008-9050-5 |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}}</ref>.

A 1992 article by [[David Avis]] and Komei Fukuda<ref>{{cite journal|url=http://www.springerlink.com/content/m7440v7p3440757u/ |author1=David Avis |author2=Komei Fukuda |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}}</ref> presents an 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]]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 [[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.