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 s, t ∈ ∂ P such that dP(s, t) ≥ (1 - ε)DP, where DP = maxs, t ∈ ε P dP(s, t) is the geodesic diameter of P.
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics