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 R3, 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

@string{ALGORITHMICA = "Algorithmica"}

@article{ahk-caspcp-02,
author =       {P.K.~Agarwal and S.~Har-Peled and M.~Karia},
title =        {Computing Approximate Shortest Paths on Convex Polytopes},
year =         2002,
journal =      ALGORITHMICA,
pages =        {227--242},
volume =       33,
number =       2
}


Last modified: Wed Jul 20 16:00:27 CDT 2011