Star Unfolding from a Geodesic Curve

Authors Stephen Kiazyk, Anna Lubiw



PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.390.pdf
  • Filesize: 1.14 MB
  • 15 pages

Document Identifiers

Author Details

Stephen Kiazyk
Anna Lubiw

Cite AsGet BibTex

Stephen Kiazyk and Anna Lubiw. Star Unfolding from a Geodesic Curve. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 390-404, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.390

Abstract

There are two known ways to unfold a convex polyhedron without overlap: the star unfolding and the source unfolding, both of which use shortest paths from vertices to a source point on the surface of the polyhedron. Non-overlap of the source unfolding is straightforward; non-overlap of the star unfolding was proved by Aronov and O'Rourke in 1992. Our first contribution is a much simpler proof of non-overlap of the star unfolding. Both the source and star unfolding can be generalized to use a simple geodesic curve instead of a source point. The star unfolding from a geodesic curve cuts the geodesic curve and a shortest path from each vertex to the geodesic curve. Demaine and Lubiw conjectured that the star unfolding from a geodesic curve does not overlap. We prove a special case of the conjecture. Our special case includes the previously known case of unfolding from a geodesic loop. For the general case we prove that the star unfolding from a geodesic curve can be separated into at most two non-overlapping pieces.
Keywords
  • unfolding
  • convex polyhedra
  • geodesic curve

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Pankaj K. Agarwal, Boris Aronov, and Catherine A. Schevon. Star unfolding of a polytope with applications. SIAM Journal on Computing, 26:1689-1713, 1997. Google Scholar
  2. Boris Aronov and Joseph O'Rourke. Nonoverlap of the star unfolding. Discrete & Computational Geometry, 8(3):219-250, 1992. Google Scholar
  3. Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Arlo Shallit, and Jonah Shallit. Zipper unfoldings of polyhedral complexes. In Proceedings of the 22nd Annual Canadian Conference on Computational Geometry (CCCG), pages 219-222, August 2010. Google Scholar
  4. Erik D. Demaine and Anna Lubiw. A generalization of the source unfolding of convex polyhedra. In Revised Papers from the 14th Spanish Meeting on Computational Geometry (EGC 2011), volume 7579 of Lecture Notes in Computer Science, pages 185-199, Alcalá de Henares, Spain, June 27-30 2012. Google Scholar
  5. Erik D. Demaine and Joseph O'Rourke. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press, New York, NY, USA, 2007. Google Scholar
  6. Albrecht Dürer. The Painter’s Manual: A Manual of Measurement of Lines, Areas, and Solids by Means of Compass and Ruler Assembled by Albrecht Dürer for the Use of All Lovers of Art with Appropriate Illustrations Arranged to be Printed in the Year MDXXV. The literary remains of Albrecht Dürer. Abaris Books, 1977. Google Scholar
  7. Kouki Ieiri, Jin-ichi Itoh, and Costin Vîlcu. Quasigeodesics and farthest points on convex surfaces. Advances in Geometry, 11(4):571-584, 2011. Google Scholar
  8. Jin-Ichi Itoh, Joseph O'Rourke, and Costin Vîlcu. Source unfoldings of convex polyhedra with respect to certain closed polygonal curves. In Proceedings of the 25th European Workshop on Computational Geometry (EuroCG), pages 61-64, 2009. Google Scholar
  9. Jin-ichi Itoh, Joseph O'Rourke, and Costin Vîlcu. Star unfolding convex polyhedra via quasigeodesic loops. Discrete & Computational Geometry, 44(1):35-54, 2010. Google Scholar
  10. Stephen Kiazyk. The star unfolding from a geodesic curve. Master’s thesis, Cheriton School of Computer Science, University of Waterloo, 2014. Google Scholar
  11. Joseph O'Rourke and Costin Vîlcu. Development of curves on polyhedra via conical existence. Computational Geometry, 47(2, Part A):149-163, 2014. Google Scholar
  12. Micha Sharir and Amir Schorr. On shortest paths in polyhedral spaces. SIAM Journal on Computing, 15(1):193-215, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail