Algorithms for geodesics on convex polytopes
Catherine A. Schevon · 1990
In this thesis we present a collection of results that deal with paths, geodesics, and shortest paths on convex polytopes. The area is rich in problems and is largely unexplored from the point of view of discrete computational geometry. We provide an overview of unfolding and folding of polytopes, and give a result on the development of closed convex polygonal curves on the surface of a convex polytope, and an empirically supported conjecture on random unfoldings. Edge sequences, or sequences of edges traversed by shortest paths on polytopes, receive a large share of attention. First, we prove bounds on the number of edge sequences that may be found on a convex polytope, and then we present an algorithm to compute them. A fundamental part of the algorithm is a data structure that records shortest path information between pairs of edges. The gap between the upper and lower bounds on the size of this data structure is presently very large. We offer a conjecture and a discussion of several issues involved in settling it. The final problem is that of finding the geodesic diameter, center, and radius of a convex polytope. The geodesic diameter of a polytope is the greatest separation between two points on the surface, where distance is determined by the shortest geodesic path between the points. Our major result here is proving that there must be at least five distinct shortest paths between any pair of points realizing the diameter, provided neither of those points coincide with polytope vertices. This leads to the result that there are a finite number, in fact a polynomial number, of possible diametral pairs, which in turn allows us to develop a polynomial time algorithm.