APPROXIMATING SHORTEST PATHS ON A CONVEX POLYTOPE IN 3 DIMENSIONS

Given a convex polytope P with n faces in R-3, points s, t is an eleme nt of partial derivative P, and a parameter 0 < epsilon less than or e qual to 1, we present an algorithm that constructs a path on partial d erivative 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 a nd 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.