Computing Approximate Shortest Paths on Convex Polytopes

Pankaj K. Agarwal, Sariel Har-Peled, and Meetesh Karia

The exact algorithms for computing a shortest path on a polyhedral
surface are slow, complicated, and numerically unstable. We have
developed and implemented a robust, efficient algorithm for computing
approximate shortest paths on a convex polyhedral surface. Given a
convex polyhedral surface P in R^{3}, two points
s, t in P, and a parameter µ > 0, it computes a path
between s and t on P whose length is at most
(1+µ) times the length of the shortest path between those
points. It first constructs in time O(n/\sqrt µ) a graph of
size O(1/µ^{4}), computes a shortest path on this
graph, and projects the path onto the surface in O(n/µ)
time, where n is the number of vertices of P. We
implemented a heuristic that considerably improves the quality of the
path.
Postscript :
PDF
Appeared in Algorithmica 33 (2), 227-242, 2002.
Also in The
16th Annu. ACM Sympos. Comput. Geom..
Presentation Presentation - postscript Presentation in Star
Office Format