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³, 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/µ⁴), 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.

Appeared in Algorithmica 33 (2), 227-242, 2002.
Also in The 16th Annu. ACM Sympos. Comput. Geom..

Postscript [PDF]

Presentation
Presentation - postscript
Presentation in Star Office Format

Program

@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: Tue Jun 20 17:18:02 EDT 2000