Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions

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 ∈ ∂P, and a parameter 0 <ε≤, it computes, in O((log n)/ε^1.5PLU1/ε³) time, a distance Δ_P(s, t), such that d_P(s, t) ≤Δ_p(s, t) ≤(1 +ε)d_P(s, t), where d_P(s, t) is the length of the shortest path between 3 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 Δ_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 ∈ ∂P such that d_P(s, t)≥(1-ε)D_P, where D_P = max_s,t∈∂P d_P(s, t) is the geodesic diameter of P.