Demaine, Erik D. ;
Hesterberg, Adam C. ;
Ku, Jason S.
Finding Closed Quasigeodesics on Convex Polyhedra
Abstract
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 (nonselfintersecting) 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²/ε² 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 constantsize 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 constanttime wbit arithmetic operations where w = Ω(lg b).
BibTeX  Entry
@InProceedings{demaine_et_al:LIPIcs:2020:12191,
author = {Erik D. Demaine and Adam C. Hesterberg and Jason S. Ku},
title = {{Finding Closed Quasigeodesics on Convex Polyhedra}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {33:133:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771436},
ISSN = {18688969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12191},
URN = {urn:nbn:de:0030drops121912},
doi = {10.4230/LIPIcs.SoCG.2020.33},
annote = {Keywords: polyhedra, geodesic, pseudopolynomial, geometric precision}
}
08.06.2020
Keywords: 

polyhedra, geodesic, pseudopolynomial, geometric precision 
Seminar: 

36th International Symposium on Computational Geometry (SoCG 2020)

Issue date: 

2020 
Date of publication: 

08.06.2020 