Approximate Shortest-Path and Geodesic Diameter on Convex Polytopes in Three Dimensions
Home Bookmarks Papers Blog

Approximate Shortest-Path and Geodesic Diameter on Convex Polytopes in Three Dimensions

Sariel Har-Peled


Given a convex polytope P with n edges in R3, we present a relatively simple algorithm that preprocesses P in O(n) time, such that, given any two points s,t on P, and a parameter 0< µ <= 1, it computes, in O( ( log (n) ) / µ1.5 + 1/µ3 ) time, a distance LP (s,t), such that dP(s,t) <= LP(s,t) <= (1+µ)dP(s,t), where dP(s,t) is the length of the shortest path between s and t on P. The algorithm also produces a polygonal path with O(1/µ1.5) segments that avoids the interior of P and has length LP(s,t).

Our second related result is: Given a convex polytope P with n edges in R3, and a parameter 0 < µ <= 1, we present an O( n + 1/µ6 )-time algorithm that computes two points s, t on P such that dP(s, t) >= (1-µ)dmP, where dmP = maxs, t on P dP(s, t) is the geodesic diameter of P.

Appeared in Discrete & Computational Geometry.
Preliminary version appeard in the 13th ACM Symp. of Comput. Geom., 1997.


Postscript : PDF
@Article{hp-aspgd-99,
  author =       "S.~Har-Peled",
  title =        {Approximate shortest paths and geodesic diameters
                  on convex polytopes in three dimensions},
  journal = DCG,
  year = 1999,
  pages = {216--231},
  volume = {21},
}

Last modified: Fri Nov 14 11:14:33 CST 2014