Approximating shortest paths on a convex polytope in three dimensions

We present an approximation algorithm that, given a convex polytope P with n faces in R³, points s, t ε ∂P, and a parameter 0 < ε ≤ 1, constructs a path on ∂P from s to t whose length is at most (1 + ε)d_P(s, t), where d_P(s, t) is the length of the shortest path between s and t on ∂P. The algorithm runs in O(n · min {1/ε^1.5, log n} + 1/ε^4.5 log(1/ε)) time, and is relatively simple to implement. We also present an extension of the algorithm that computes approximate shortest paths from a given source point on ∂P to all vertices of P.