Home | Bookmarks | Papers | Blog |
Given a convex polytope P with n faces in R3, 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+ µ)dP(s,t), where dP(s,t) is the length of the shortest path between s and t on P. The algorithm runs in O(n log 1/ µ + 1/ µ3) time, and is relatively simple to implement. The running time is O(n + 1/ µ3) 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} }