Approximating Shortest Paths on a Convex Polytope in Three Dimensions

# 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 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