## Abstract

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 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 ℝ^{3}, and a parameter 0 < ε ≤ 1, we present an O(n + 1/ε^{5})-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.

Original language | English (US) |
---|---|

Pages (from-to) | 217-231 |

Number of pages | 15 |

Journal | Discrete and Computational Geometry |

Volume | 21 |

Issue number | 2 |

DOIs | |

State | Published - Mar 1999 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics