Analysis for shortest path algorithmon convex polytope in E 3
Young Soo Lee, Eunseok Lee · Electronics Letters · 2000
Hershberger and Suri proposed an extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions in 1998. 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. Their algorithm, ShortestPath, produces a path of length at most 2dP(p, q) in time O(n). This algorithm is revised, and achieves a ratio of 1.786.