Finding Closed Quasigeodesics on Convex Polyhedra
share
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^2 ε^2L ℓ 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 with the model of computation, introducing the O(1)-expression RAM and showing that it can be implemented in the standard word RAM.
READ FULL TEXT