**Reference**:- Erik D. Demaine, Adam C. Hesterberg, and Jason S. Ku, “Finding Closed Quasigeodesics on Convex Polyhedra”, in
*Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020)*, June 23–26, 2020, 33:1–33:13. **Abstract**:-
A
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((*closed quasigeodesic**n*^{2}/ ε^{2}) (*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*). **Comments**:- The full version of this paper is available as arXiv:2008.00589. The paper is also available from LIPIcs. Our presentation is available on YouTube.
**Length**:- The paper is 13 pages.
**Availability**:- The paper is available in PDF (657k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.