We generalize our optimal-time algorithm for computing (an implicitrepresentation of) the shortest-path map from a fixed source s onthe surface of a convex polytope P into three scenarios where P is a possibly nonconvex polyhedron. In the first scenario, ∂ P is a terrain whose maximal facet slope is bounded by a constant. In the second scenario P is an uncrowded polyhedron -- each axis-parallel square h of length l(h) whose smallest Euclidean distance to a vertex of P is at least l(h) is intersected by at most O(1) facets of ∂ P -- an input model that, as we show, is a generalization of the well-known low density model. In the third scenario P is self-conforming -- that is, for each surface edge e of P, there is only a constant number of facets of ∂ P within shortest path distance O(|e|); in particular, it includes the case that each facet of ∂ P is fat and each vertex is incident to at most O(1) facets of ∂ P. In all the above cases the algorithm runs in O(n log n) time and space, where n is the number of edges of P, and produces an implicit representation of the shortest-path map, so that the shortest path from s to any query point q can be determined in O(log n) time. We also show that the self-conforming model allows for a major simplification of the algorithm.

We present an optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source s on the surface of a convex polytope P in three dimensions. Our algorithm runs in O(n log n) timeandrequires O(n log n) space, where n is the number of edges of P. The algorithm is based on the O(n log n) algorithm of Hershberger and Suri for shortest paths in the plane [11], and similarly follows the continuous Dijkstra paradigm, which propagates a “wavefront ” from s along ∂P. Thisiseffected by generalizing the concept of conforming subdivision of the free space used in [11], and adapting it for the case of a convex polytope in R 3, allowing the algorithm to accomplish the propagation in discrete steps, between the “transparent” edges of the subdivision. The algorithm constructs a dynamic version of Mount’s data structure [16] that implicitly encodes the shortest paths from s to all other points of the surface. This structure allows us to answer single-source shortest-path queries, where the length of the path, as well as its combinatorial type, can be reported in O(log n) time; the actual path π can be reported in additional O(k) time, where k is the number of polytope edges crossed by π. The algorithm generalizes to the case of m source points to yield an implicit representation of the geodesic Voronoi diagram of m sites on the surface of P, in time O((n + m)log(n + m)), so that the site closest to a query point can be reported in time O(log(n + m)).