Nonoverlap of the star unfolding (Q1199127): Difference between revisions

The results of this paper improve several algorithms connected with shortest path problems in three-dimensional space. The star unfolding of a convex polytope with respect to a point \(x\) on its surface is obtained by cutting the surface along the shortest paths from \(x\) to every vertex, and flattering the surface on the plane. It is proved, that the star unfolding does not self-overlap and that the ridge tree in the unfolding (the locus of points with more than one shortest path from \(x\)), is precisely the Voronoi diagram of the images of \(x\), restricted to the unfolding. This gives for example the following algorithm for constructing the ridge tree: find shortest paths to all corners, build the star unfolding in the plane, and compute the Voronoi diagram of the set of source images. Algorithms for shortest-path edge sequences and the geodesic diameter of a polygon are given.