2020/08/03 by Demaine, Erik D., Hesterberg, Adam C., Ku, Jason S.
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.2008.00589
A closed quasigeodesic is a closed curve on the surface of a polyhedron with at most 180^∘ of surface on both sides at all points; such curves 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 also establishes a pseudopolynomial upper bound on the total number of visits to faces (number of line segments), namely, O((n L2)/(ε2 ℓ2)) where n is the number of vertices of the polyhedron, ε is the minimum curvature of a vertex, L is the length of the longest edge, and ℓ is the smallest distance within a face between a vertex and a nonincident edge (minimum feature size of any face). On the real RAM, the algorithm's running time is also pseudopolynomial, namely O((L2)/(ε2 ℓ2) n \lg n). On a word RAM, the running time grows to O(\fracb2 Δ36 L146ε98 ℓ146 n \lg n ⋅ 2O(|R|)), where Δ≤ n is the polyhedron's maximum vertex degree, assuming the polyhedron's intrinsic geometry is given by constant-size radical expressions with b-bit integers and at most |R| distinct square-roots. Along the way, we introduce the expression RAM model of computation, formalizing a connection between the real RAM and word RAM hinted at by past work on exact geometric computation.