Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions

Given a convex polytope P with n edges in ℝ³, 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 < ε ≤ 1, it computes, in O((log n)/ε^1.5 + 1/ε³) 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 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 Δ_P(s, t). Our second related result is: Given a convex polytope P with n edges in ℝ³, 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.