| Abstract | We presentan algorithm for determining the shortest path between a source and a destinationon an arbitrary (possibly nonconvex) polyhedralsurface. The path is constrained to lie on the surface, and
distances are measured according to the Euclidean metric. Our algorithm runs in time O(n log n) and
requires O(n2) space, where n is the number of edges of the surface. After we run our algorithm, the distance
from the source to any other destination may be determined using standard techniques in time O(log n) by
locating the destination in the subdivision created by the algorithm. The actual shortest path from the source
to a destination can bereported in time O(k+log n), where k is the number of faces crossed by the path.
The algorithm generalizes to the case of multiple source points to build the Voronoi diagram on the surface,
where n is now the maximum of the number of vertices and the number of sources.
|
