Technical Report Number
We propose a n extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions. Given a convex polytope P with n vertices and two points p,q on its surface, let dp (p,q) denote the shortest path distance between p and q on the surface of P. Our algorithm produces a path of length at most 2 × dp(p,q) in time O(n). Extending this results, we can also compute ana pproximation of the shortest path tree rooted at an arbitrary point χ Є P in time O(n log n). In the approximate tree, the distance between a vertex ν Є P and χ is at most c × dp(χ, ν), where c = 2.38(1+ε) for any fixed ε > 0. The best algorithm for computing an exact shortest path on a convex polytopt take Ω(n2) time in the worst case; in addition, they are too complicated to be suitable in practice. We can also get a weak approximation result in the general case of k disjoint convex polyhedra: in O(n) time our algorithm gives a path of length at most 2k times the optimal.
Hershberger, John and Suri, Subhash, "Practical Methods for Approximating Shortest Paths on a Convex Polytope in R3" Report Number: WUCS-94-31 (1994). All Computer Science and Engineering Research.
Permanent URL: http://dx.doi.org/10.7936/K7XW4H09