Practical methods for approximating shortest paths on a convex polytope in R3

We propose an 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 2dp(p, q) in time O(n). Extending this result, we can also compute an approximation of the shortest path tree rooted at an arbitrary point x is an element of P in time O(n log n). In the approximate tree, the distance between a vertex v is an element of P and ar is at most cdp(x, v), where c = 2.38(1 + epsilon) for any fixed epsilon > 0. The best algorithms for computing an exact shortest path on a convex polytope take Omega(n(2)) 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 h-disjoint convex polyhedra: in O(n) time our algorithm gives a path of length at most 2k times the optimal. (C) 1998 Elsevier Science B.V.