LIPIcs.SoCG.2022.27.pdf
- Filesize: 4.31 MB
- 16 pages
Document
Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres
Authors
-
Part of:
Volume:
38th International Symposium on Computational Geometry (SoCG 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-01
File
Document Identifiers
Acknowledgements
We thank Francis Lazarus for insightful discussions, and Joseph O'Rourke and the anonymous reviewers for helpful comments.
Cite AsGet BibTex
Jean Chartier and Arnaud de Mesmay. Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.27
https://doi.org/10.4230/LIPIcs.SoCG.2022.27
Abstract
A closed quasigeodesic on a convex polyhedron is a closed curve that is locally straight outside of the vertices, where it forms an angle at most π on both sides. While the existence of a simple closed quasigeodesic on a convex polyhedron has been proved by Pogorelov in 1949, finding a polynomial-time algorithm to compute such a simple closed quasigeodesic has been repeatedly posed as an open problem. Our first contribution is to propose an extended definition of quasigeodesics in the intrinsic setting of (not necessarily convex) polyhedral spheres, and to prove the existence of a weakly simple closed quasigeodesic in such a setting. Our proof does not proceed via an approximation by smooth surfaces, but relies on an adapation of the disk flow of Hass and Scott to the context of polyhedral surfaces. Our second result is to leverage this existence theorem to provide a finite algorithm to compute a weakly simple closed quasigeodesic on a polyhedral sphere. On a convex polyhedron, our algorithm computes a simple closed quasigeodesic, solving an open problem of Demaine, Hersterberg and Ku.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Quasigeodesic
- polyhedron
- curve-shortening process
- disk flow
- weakly simple
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Hugo A Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D Tóth. Recognizing weakly simple polygons. Discrete & Computational Geometry, 58(4):785-821, 2017. URL: https://doi.org/10.1007/s00454-017-9918-3.
-
Alexandr D Alexandrov. Convex polyhedra. Springer Science & Business Media, 2005.
-
Werner Ballmann. Der Satz von Lusternik und Schnirelmann. Bonner Math. Schriften, 102:1-25, 1978.
-
Werner Ballmann, Gudlaugur Thorbergsson, and Wolfgang Ziller. On the existence of short closed geodesics and their stability properties. In Seminar On Minimal Submanifolds.(AM-103), Volume 103, pages 53-64. Princeton University Press, 1983.
- George David Birkhoff. Dynamical systems, volume 9 of Colloquium Publications. American Mathematical Soc., 1927. URL: https://doi.org/10.1016/B978-044450871-3/50149-2.
- Heinz Bruggesser and Peter Mani. Shellable decompositions of cells and spheres. Mathematica Scandinavica, 29(2):197-205, 1971. URL: https://doi.org/10.7146/math.scand.a-11045.
-
Dmitri Burago, Yuri Burago, and Sergei Ivanov. A course in metric geometry, volume 33. American Mathematical Society, 2001.
-
Yuriy Dmitrievich Burago and Viktor Abramovich Zalgaller. Isometric piecewise-linear embeddings of two-dimensional manifolds with a polyhedral metric into ℝ³. Algebra i analiz, 7(3):76-95, 1995.
- Erin Wolf Chambers, Gregory R Chambers, Arnaud de Mesmay, Tim Ophelders, and Regina Rotman. Constructing monotone homotopies and sweepouts. Journal of Differential Geometry, 119(3):383-401, 2021. URL: https://doi.org/10.4310/jdg/1635368350.
- Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Proceedings of the twenty-sixth annual ACM-SIAM Symposium on Discrete Algorithms, pages 1655-1670. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973730.110.
- Jean Chartier and Arnaud de Mesmay. Finding weakly simple closed quasigeodesics on polyhedral spheres, 2022. URL: http://arxiv.org/abs/2203.05853.
- Erik D Demaine, Adam C Hesterberg, and Jason S Ku. Finding closed quasigeodesics on convex polyhedra. In 36th International Symposium on Computational Geometry (SoCG 2020), pages 33:1-33:13. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.1007/b137434.
- Erik D Demaine and Joseph O'Rourke. Geometric folding algorithms: linkages, origami, polyhedra. Cambridge University Press, 2007. URL: https://doi.org/10.1017/CBO9780511735172.
- Jeff Erickson and Amir Nayyeri. Tracing compressed curves in triangulated surfaces. Discrete & Computational Geometry, 49(4):823-863, 2013. URL: https://doi.org/10.1007/s00454-013-9515-z.
- Matthew A Grayson. Shortening embedded curves. Annals of Mathematics, 129(1):71-111, 1989. URL: https://doi.org/10.2307/1971486.
- Joel Hass and Peter Scott. Shortening curves on surfaces. Topology, 33(1):25-43, 1994. URL: https://doi.org/10.1016/0040-9383(94)90033-7.
- Daniel Kane, Gregory N Price, and Erik D Demaine. A pseudopolynomial algorithm for Alexandrov’s theorem. In Workshop on Algorithms and Data Structures, pages 435-446. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03367-4_38.
-
L Lyusternik and Lev Schnirelmann. Sur le problème de trois géodésiques fermées sur les surfaces de genre 0. CR Acad. Sci. Paris, 189(269):271, 1929.
-
Aleksei Vasil'evich Pogorelov. Quasi-geodesic lines on a convex surface. Matematicheskii Sbornik, 67(2):275-306, 1949. English translation in American Mathematical Society Translations 74, 1952.
-
Henri Poincaré. Sur les lignes géodésiques des surfaces convexes. Transactions of the American Mathematical Society, 6(3):237-274, 1905.
- Nicholas Sharp, Yousuf Soliman, and Keenan Crane. Navigating intrinsic triangulations. ACM Transactions on Graphics (TOG), 38(4):1-16, 2019. URL: https://doi.org/10.1145/3306346.3322979.
- Günter M Ziegler. Lectures on polytopes, volume 152 of Graduate Texts in Mathematics. Springer Science & Business Media, 2012. URL: https://doi.org/10.1007/978-1-4613-8431-1.