Finding closed quasigeodesics on convex polyhedra
A closed quasigeodesic is a closed loop on the surface of a polyhedron with at most 180◦ of surface on both sides at all points; such loops can be locally unfolded straight. In 1949, Pogorelov proved that every convex polyhedron has at least three (non-self-intersecting) closed quasigeodesics, but t...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Schloss Dagstuhl, Leibniz Center for Informatics
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129938 |
| _version_ | 1811086245143511040 |
|---|---|
| author | Demaine, Erik D Hesterberg, Adam Classen Ku, Jason S |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D Hesterberg, Adam Classen Ku, Jason S |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | A closed quasigeodesic is a closed loop on the surface of a polyhedron with at most 180◦ of surface on both sides at all points; such loops can be locally unfolded straight. In 1949, Pogorelov proved that every convex polyhedron has at least three (non-self-intersecting) closed quasigeodesics, but the proof relies on a nonconstructive topological argument. We present the first finite algorithm to find a closed quasigeodesic on a given convex polyhedron, which is the first positive progress on a 1990 open problem by O'Rourke and Wyman. The algorithm's running time is pseudopolynomial, namely O ( nε22 L` b ) time, where ε is the minimum curvature of a vertex, L is the length of the longest edge, ` is the smallest distance within a face between a vertex and a nonincident edge (minimum feature size of any face), and b is the maximum number of bits of an integer in a constant-size radical expression of a real number representing the polyhedron. We take special care in the model of computation and needed precision, showing that we can achieve the stated running time on a pointer machine supporting constant-time w-bit arithmetic operations where w = Ω(lg b). |
| first_indexed | 2024-09-23T13:23:08Z |
| format | Article |
| id | mit-1721.1/129938 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:23:08Z |
| publishDate | 2021 |
| publisher | Schloss Dagstuhl, Leibniz Center for Informatics |
| record_format | dspace |
| spelling | mit-1721.1/1299382022-10-01T14:57:01Z Finding closed quasigeodesics on convex polyhedra Demaine, Erik D Hesterberg, Adam Classen Ku, Jason S Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science A closed quasigeodesic is a closed loop on the surface of a polyhedron with at most 180◦ of surface on both sides at all points; such loops can be locally unfolded straight. In 1949, Pogorelov proved that every convex polyhedron has at least three (non-self-intersecting) closed quasigeodesics, but the proof relies on a nonconstructive topological argument. We present the first finite algorithm to find a closed quasigeodesic on a given convex polyhedron, which is the first positive progress on a 1990 open problem by O'Rourke and Wyman. The algorithm's running time is pseudopolynomial, namely O ( nε22 L` b ) time, where ε is the minimum curvature of a vertex, L is the length of the longest edge, ` is the smallest distance within a face between a vertex and a nonincident edge (minimum feature size of any face), and b is the maximum number of bits of an integer in a constant-size radical expression of a real number representing the polyhedron. We take special care in the model of computation and needed precision, showing that we can achieve the stated running time on a pointer machine supporting constant-time w-bit arithmetic operations where w = Ω(lg b). 2021-02-22T15:16:54Z 2021-02-22T15:16:54Z 2020-06 2020-12-09T18:18:17Z Article http://purl.org/eprint/type/ConferencePaper 1868-8969 9783959771436 https://hdl.handle.net/1721.1/129938 Demaine, Erik D. et al. “Finding closed quasigeodesics on convex polyhedra.” 36th International Symposium on Computational Geometry, June 2020, virtual, Schloss Dagstuhl and Leibniz Center for Informatics, June 2020. © 2020 The Author(s) en 10.4230/LIPIcs.SoCG.2020.33 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 3.0 unported license https://creativecommons.org/licenses/by/3.0/ application/pdf Schloss Dagstuhl, Leibniz Center for Informatics DROPS |
| spellingShingle | Demaine, Erik D Hesterberg, Adam Classen Ku, Jason S Finding closed quasigeodesics on convex polyhedra |
| title | Finding closed quasigeodesics on convex polyhedra |
| title_full | Finding closed quasigeodesics on convex polyhedra |
| title_fullStr | Finding closed quasigeodesics on convex polyhedra |
| title_full_unstemmed | Finding closed quasigeodesics on convex polyhedra |
| title_short | Finding closed quasigeodesics on convex polyhedra |
| title_sort | finding closed quasigeodesics on convex polyhedra |
| url | https://hdl.handle.net/1721.1/129938 |
| work_keys_str_mv | AT demaineerikd findingclosedquasigeodesicsonconvexpolyhedra AT hesterbergadamclassen findingclosedquasigeodesicsonconvexpolyhedra AT kujasons findingclosedquasigeodesicsonconvexpolyhedra |