Given a convex polytope P with n edges in
R^{3}, we present
a relatively simple algorithm that preprocesses P in O(n)
time, such that, given any two points s,t on P, and a
parameter 0< µ <= 1, it computes, in O( ( log (n) ) /
µ^{1.5} + 1/µ^{3} ) time, a distance L_{P} (s,t), such
that d_{P}(s,t) <= L_{P}(s,t) <= (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 also produces a polygonal path with
O(1/µ^{1.5}) segments that avoids the interior of P and has
length L_{P}(s,t).

Our second related result is: Given a convex polytope P
with n
edges in R^{3}, and a parameter 0 < µ <= 1, we present an
O( n + 1/µ^{6} )-time algorithm that computes
two points s, t on
P such that d_{P}(s, t) >=
(1-µ)dm_{P}, where dm_{P}
= max_{s, t on P} d_{P}(s, t) is the geodesic diameter of
P.