Content deleted Content added
→References: authorlink1=David Avis |
→Vertex enumeration: link Avis |
||
Line 43:
===Vertex enumeration===
The criss-cross algorithm was used in an an algorithm for [[Vertex enumeration problem|enumerating all the vertices of a polytope]], which was published by [[David Avis]] and Komei Fukuda in 1992.<ref>{{harvtxt|Avis|Fukuda|1992|p=297}}</ref> Avis and Fukuda presented an algorithm which finds the ''v'' vertices of a [[polyhedron]] defined by a nondegenerate system of ''n'' [[linear inequality|linear inequalities]] in ''D'' [[dimension (vector space)|dimension]]s (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]].<ref>The ''v'' vertices in a simple arrangement of ''n'' [[hyperplane]]s in ''D'' dimensions can be found in O(''n''<sup>2</sup>''Dv'') time and O(''nD'') [[space complexity]].</ref>
===Oriented matroids===
| |||