Shortest Path Problems on a Polyhedral Surface

摘要

We describe algorithms to compute edge sequences, a shortest path map, and the Frechet distance for a convex polyhedral surface. Distances on the surface are measured by the length of a Euclidean shortest path. We describe how the star unfolding changes as a source point slides continuously along an edge of the convex polyhedral surface. We describe alternative algorithms to the edge sequence algorithm of Agarwal et al. (SIAM J. Comput. 26(6): 1689-1713, 1997) for a convex polyhedral surface. Our approach uses persistent trees, star unfoldings, and kinetic Voronoi diagrams. We also show that the core of the star unfolding can overlap itself when the polyhedral surface is non-convex.