Given a convex polytope P with n edges in ℝ3, 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/ε3) time, a distance ΔP(s, t), such that dP(s, t) ≤ ΔP(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 ΔP(s, t). Our second related result is: Given a convex polytope P with n edges in ℝ3, and a parameter 0 < ε ≤ 1, we present an O(n + 1/ε5)-time algorithm that computes two points 𝔰, 𝔱 ∈ ∂ P such that dP(𝔰, 𝔱) ≥ (1 – ε)𝒟P, where 𝒟P = maxs, t ∈ ∂PdP(s, t) is the geodesic diameter of P.
