Approximating Shortest Paths on a Convex Polytope in Three Dimensions

Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir and Kasturi R. Varadarajan

Given a convex polytope P with n faces in R³, points s,t on P, and a parameter 0< µ <= 1, we present an algorithm that constructs a path on P from s to t whose length is at most (1+ µ)d_P(s,t), where d_P(s,t) is the length of the shortest path between s and t on P. The algorithm runs in O(n log 1/ µ + 1/ µ³) time, and is relatively simple to implement. The running time is O(n + 1/ µ³) if we only want the approximate shortest path distance and not the path itself. We also present an extension of the algorithm that computes approximate shortest path distances from a given source point on P to all vertices of P.

In J. ACM, 44 (1997), 567-584.
Preliminary version appeared in the 12th Annual ACM Symposium on COMPUTATIONAL GEOMETRY.

Full version: PDF.

@Article{ahsv-aspcp-97
, author =      "P.~K.~Agarwal and S.~Har-Peled and 
                 M.~Sharir and K.~R.~Varadarajan"
, title =       "Approximate Shortest Paths on a Convex Polytope in 
                 Three Dimensions"
, journal =      "J. Assoc. Comput. Mach."
, year =         1997
, volume = {44}
, pages = {567--584}
}