Home | Bookmarks | Papers | Blog |
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.
@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}, }