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

Sariel Har-Peled

Given a convex polytope P with n edges in R³, 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/µ³ ) time, a distance L_P (s,t), such that d_P(s,t) <= L_P(s,t) <= (1+µ)d_P(s,t), where d_P(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 L_P(s,t).

Our second related result is: Given a convex polytope P with n edges in R³, and a parameter 0 < µ <= 1, we present an O( n + 1/µ⁶ )-time algorithm that computes two points s, t on P such that d_P(s, t) >= (1-µ)dm_P, where dm_P = max_{s, t on P} d_P(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},
}