{{Short description|Net obtained by cutting a polyhedron}} In computational geometry, the '''star unfolding''' of a convex polyhedron is a net obtained by cutting the polyhedron along geodesics (shortest paths) through its faces. It has also been called the '''inward layout''' of the polyhedron, or the '''Alexandrov unfolding''' after Aleksandr Danilovich Aleksandrov, who first considered it.{{r|do}}
==Description== In more detail, the star unfolding is obtained from a polyhedron <math>P</math> by choosing a starting point <math>p</math> on the surface of <math>P</math>, in general position, meaning that there is a unique shortest geodesic from <math>p</math> to each vertex of <math>P</math>.{{r|ao|aaos|ch}} The star polygon is obtained by cutting the surface of <math>P</math> along these geodesics, and unfolding the resulting cut surface onto a plane. The resulting shape forms a simple polygon in the plane.{{r|ao|aaos}}
The star unfolding may be used as the basis for polynomial time algorithms for various other problems involving geodesics on convex polyhedra.{{r|ao|aaos}}
==Related unfoldings== The star unfolding should be distinguished from another way of cutting a convex polyhedron into a simple polygon net, the source unfolding. The source unfolding cuts the polyhedron at points that have multiple equally short geodesics to the given base point <math>p</math>, and forms a polygon with <math>p</math> at its center, preserving geodesics from <math>p</math>. Instead, the star unfolding cuts the polyhedron along the geodesics, and forms a polygon with multiple copies of <math>p</math> at its vertices.{{r|aaos}} Despite their names, the source unfolding always produces a star-shaped polygon, but the star unfolding does not.{{r|do}}
Generalizations of the star unfolding using a geodesic or quasigeodesic in place of a single base point have also been studied.{{r|iov|kl}} Another generalization uses a single base point, and a system of geodesics that are not necessarily shortest geodesics.{{r|as}}
Neither the star unfolding nor the source unfolding restrict their cuts to the edges of the polyhedron. It is an open problem whether every polyhedron can be cut and unfolded to a simple polygon using only cuts along its edges.{{r|aaos}}
==References== <references>
<ref name=aaos>{{citation | last1 = Agarwal | first1 = Pankaj K. | author1-link = Pankaj K. Agarwal | last2 = Aronov | first2 = Boris | author2-link = Boris Aronov | last3 = O'Rourke | first3 = Joseph | author3-link = Joseph O'Rourke (professor) | last4 = Schevon | first4 = Catherine A. | doi = 10.1137/S0097539793253371 | issue = 6 | journal = SIAM Journal on Computing | mr = 1484151 | pages = 1689–1713 | title = Star unfolding of a polytope with applications | volume = 26 | year = 1997}}</ref>
<ref name=ao>{{citation | last1 = Aronov | first1 = Boris | author1-link = Boris Aronov | last2 = O'Rourke | first2 = Joseph | author2-link = Joseph O'Rourke (professor) | doi = 10.1007/BF02293047 | issue = 3 | journal = Discrete & Computational Geometry | mr = 1174356 | pages = 219–250 | title = Nonoverlap of the star unfolding | volume = 8 | year = 1992| doi-access = free }}</ref>
<ref name=as>{{citation | last1 = Alam | first1 = Md. Ashraful | last2 = Streinu | first2 = Ileana | author2-link = Ileana Streinu | editor1-last = Botana | editor1-first = Francisco | editor2-last = Quaresma | editor2-first = Pedro | contribution = Star-unfolding polygons | doi = 10.1007/978-3-319-21362-0_1 | mr = 3440706 | pages = 1–20 | publisher = Springer | series = Lecture Notes in Computer Science | title = Automated Deduction in Geometry: 10th International Workshop, ADG 2014, Coimbra, Portugal, July 9-11, 2014, Revised Selected Papers | volume = 9201 | year = 2015| isbn = 978-3-319-21361-3 }}</ref>
<ref name=ch>{{citation | last1 = Chen | first1 = Jindong | last2 = Han | first2 = Yijie | contribution = Shortest paths on a polyhedron | doi = 10.1145/98524.98601 | publisher = ACM Press | title = Proceedings of the 6th Annual Symposium on Computational Geometry (SoCG 1990) | year = 1990| pages = 360–369 | s2cid = 7498502 | doi-access = free | isbn = 0-89791-362-0 }}</ref>
<ref name=do>{{citation | last1 = Demaine | first1 = Erik | author1-link = Erik Demaine | last2 = O'Rourke | first2 = Joseph | author2-link = Joseph O'Rourke (professor) | contribution = 24.3 Star unfolding | isbn = 978-0-521-71522-5 | pages = 366–372 | publisher = Cambridge University Press | title = Geometric Folding Algorithms | title-link = Geometric Folding Algorithms | year = 2007}}</ref>
<ref name=iov>{{citation | last1 = Itoh | first1 = Jin-ichi | last2 = O'Rourke | first2 = Joseph | author2-link = Joseph O'Rourke (professor) | last3 = Vîlcu | first3 = Costin | doi = 10.1007/s00454-009-9223-x | issue = 1 | journal = Discrete & Computational Geometry | mr = 2639817 | pages = 35–54 | title = Star unfolding convex polyhedra via quasigeodesic loops | volume = 44 | year = 2010| doi-access = free | arxiv = 0707.4258 }}</ref>
<ref name=kl>{{citation | last1 = Kiazyk | first1 = Stephen | last2 = Lubiw | first2 = Anna | author2-link = Anna Lubiw | doi = 10.1007/s00454-016-9795-1 | issue = 4 | journal = Discrete & Computational Geometry | mr = 3561798 | pages = 1018–1036 | title = Star unfolding from a geodesic curve | volume = 56 | year = 2016| hdl = 10012/8935 | s2cid = 34942363 | url = https://drops.dagstuhl.de/opus/volltexte/2015/5138/ | hdl-access = free }}</ref>
</references>
{{Mathematics of paper folding}}
Category:Polygons Category:Polyhedra Category:Computational geometry