Approximating shortest paths on a convex polytope in three dimensions

Given a convex polytope P with n faces in R-3, points s, t is an element of partial derivative P, and a parameter 0 < epsilon less than or equal to 1, we present an algorithm that constructs a path on partial derivative P from s to t whose length is at most (1 + epsilon)d(P)(s, t), where d(P)(s, t) is the length of the shortest path between s and t on partial derivative P. The algorithm runs in O(n log 1/epsilon + 1/epsilon(3)) time, and is relatively simple. The running time is O(n + 1/epsilon(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 partial derivative P to all vertices of P.