Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Vertex enumeration problem
open-in-new
<h2 id="computational-complexity">Computational complexity</h2> <p>The <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity</a> of the problem is a subject of research in <a href="/facts/Computer_science/lN3pEyPz">computer science</a>. 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.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p>A 1992 article by <a href="/facts/David_Avis/ofybefml">David Avis</a> and <a href="/facts/Komei_Fukuda/H88HI0Q4">Komei Fukuda</a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> presents a <a href="/facts/Reverse-search_algorithm/Lz62WVGo">reverse-search algorithm</a> which finds the <i>v</i> vertices of a polytope defined by a nondegenerate system of <i>n</i> inequalities in <i>d</i> dimensions (or, dually, the <i>v</i> <a href="/facts/Facet/E3dBT4u9">facets</a> of the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> of <i>n</i> points in <i>d</i> dimensions, where each facet contains exactly <i>d</i> given points) in time <a href="/facts/Big_Oh_notation/weFFjSWg">O</a>(<i>ndv</i>) and <a href="/facts/Space_complexity/nsnAW5cV">space</a> O(<i>nd</i>). The <i>v</i> vertices in a simple arrangement of <i>n</i> <a href="/facts/Hyperplane/2s2ycYYd">hyperplanes</a> in <i>d</i> dimensions can be found in O(<i>n</i>2<i>dv</i>) time and O(<i>nd</i>) space complexity. The Avis–Fukuda algorithm adapted the <a href="/facts/Criss-cross_algorithm/XnLPc5tW">criss-cross algorithm</a> for oriented matroids. </p> <h2 id="notes">Notes</h2> <ul><li><a href="/facts/David_Avis/ofybefml">Avis, David</a>; <a href="/facts/Komei_Fukuda/H88HI0Q4">Fukuda, Komei</a> (December 1992). <a href="https://doi.org/10.1007%2FBF02293050">"A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra"</a>. <i><a href="/facts/Discrete_and_Computational_Geometry/wVPxzUWo">Discrete and Computational Geometry</a></i>. 8 (1): 295–313. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02293050">10.1007/BF02293050</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1174359">1174359</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Eric W. Weisstein CRC Concise Encyclopedia of Mathematics, 2002, ISBN 1-58488-347-2, p. 3154, article "vertex enumeration" <a href="/wiki/Eric_W._Weisstein" target="_blank">/wiki/Eric_W._Weisstein</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Leonid Khachiyan; Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich (March 2008). "Generating All Vertices of a Polyhedron Is Hard". Discrete and Computational Geometry. 39 (1–3): 174–190. doi:10.1007/s00454-008-9050-5. <a href="https://doi.org/10.1007%2Fs00454-008-9050-5" target="_blank">https://doi.org/10.1007%2Fs00454-008-9050-5</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>David Avis; Komei Fukuda (December 1992). "A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra". Discrete and Computational Geometry. 8 (1): 295–313. doi:10.1007/BF02293050. <a href="https://doi.org/10.1007%2FBF02293050" target="_blank">https://doi.org/10.1007%2FBF02293050</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>