Given a convex polytope P with n faces in R^{3},
points s,t on P,
and a parameter 0< µ <= 1, we present an algorithm that
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 log 1/ µ + 1/ µ^{3})
time, and is relatively simple to
implement. The running time is O(n + 1/ µ^{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 P
to all vertices of P.

@Article{ahsv-aspcp-97
, author = "P.~K.~Agarwal and S.~Har-Peled and
M.~Sharir and K.~R.~Varadarajan"
, title = "Approximate Shortest Paths on a Convex Polytope in
Three Dimensions"
, journal = "J. Assoc. Comput. Mach."
, year = 1997
, volume = {44}
, pages = {567--584}
}