Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions

Given a convex polytope P with n edges in R-3, we present a relatively simp le algorithm that preprocesses P in O(n) time, such that, given any two poi nts s, t is an element of partial derivative P, and a parameter 0 < epsilon less than or equal to 1, it computes, in O((log n)/epsilon(1.5) + 1/epsilo n(3)) time, a distance Delta(P)(s, t), such that d(P)(s, t) less than or eq ual to Delta(P)(s, t) less than or equal to (1 + epsilon)d(P)(s, t), where d(P)(s, t) is the length of the shortest path between s and t on partial de rivative P. The algorithm also produces a polygonal path with O(1/epsilon(1 .5)) segments that avoids the interior of P and has length Delta(P)(s, t). Our second related result is: Given a convex polytope P with n edges in R-3 , and a parameter O < epsilon less than or equal to 1, we present an O(n 1/epsilon(5))-time algorithm that computes two points s, t is an element of partial derivative P such that d(P)(s, t) greater than or equal to (1 - ep silon)D-P, where D-P = max(s,t is an element of partial derivative P) d(P)( s, t) is the geodesic diameter of P.