文章基本信息
- 标题：Finding Closed Quasigeodesics on Convex Polyhedra
- 本地全文：下载
- 作者：Erik D. Demaine ; Adam C. Hesterberg ; Jason S. Ku 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：164
- 页码：33:1-33:13
- DOI：10.4230/LIPIcs.SoCG.2020.33
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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).
- 关键词：polyhedra; geodesic; pseudopolynomial; geometric precision
