Abstract.
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 d P (s,t) \(\leq\) Δ P (s,t) \(\leq\) (1+ɛ )d P (s,t) , where d P (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) .
Our second related result is: Given a convex polytope P with n edges in \(\Bbb R\) 3 , and a parameter 0 < \(\varepsilon \leq\) 1, we present an O (n + 1/ ɛ 5 )-time algorithm that computes two points \({\frak{s}}, {\frak{t}} \in {\partial}{P}\) such that \(d_P({\frak{s}}, {\frak{t}}) \geq (1-{\varepsilon}){\cal D}_P\) , where \({\cal D}_P = \max_{s, t \in {\partial}{P}} d_P(s, t)\) is the geodesic diameter of P .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received April 8, 1997, and in revised form August 3, 1997.
Rights and permissions
About this article
Cite this article
Har-Peled, S. Approximate Shortest Paths and Geodesic Diameter on a Convex Polytope in Three Dimensions . Discrete Comput Geom 21, 217–231 (1999). https://doi.org/10.1007/PL00009417
Issue Date:
DOI: https://doi.org/10.1007/PL00009417