License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.33
URN: urn:nbn:de:0030-drops-121912
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12191/
Go to the corresponding LIPIcs Volume Portal

Demaine, Erik D. ; Hesterberg, Adam C. ; Ku, Jason S.

Finding Closed Quasigeodesics on Convex Polyhedra

pdf-format:
LIPIcs-SoCG-2020-33.pdf (0.7 MB)

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 (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²/ε² 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).

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:1--33:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12191},
  URN =		{urn:nbn:de:0030-drops-121912},
  doi =		{10.4230/LIPIcs.SoCG.2020.33},
  annote =	{Keywords: polyhedra, geodesic, pseudopolynomial, geometric precision}
}

Keywords: polyhedra, geodesic, pseudopolynomial, geometric precision
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI