Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions
Sariel Har-Peled · 1997
Given a convex polytope P with n edges in \(\Bbb R\)3 , we present a relatively simple algorithm that preprocesses P in O(n) time, such that, given any two points \(s,t \in \partial P\) , and a parameter 0 < \(\varepsilon \le\) 1, it computes, in O(log n) /ɛ1.5 + 1/ ɛ3 ) time, a distance ΔP(s,t) , such that dP(s,t)\(\leq\)ΔP(s,t)\(\leq\) (1+ɛ )dP(s,t) , where dP(s,t) is the length of the shortest path between s and t on \(\partial{P}\) . The algorithm also produces a polygonal path with O (1/ɛ1.5 ) segments that avoids the interior of P and has length ΔP(s,t) .