## Abstract

Given a convex polytope P with n edges in R^{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 <ε≤, it computes, in O((log n)/ε^{1.5}PLU1/ε^{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 3 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 R^{3} and a parameter 0<ε≤1, we present an O(n+1/ε^{6})-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 | 359-365 |

Number of pages | 7 |

DOIs | |

State | Published - 1997 |

Externally published | Yes |

Event | Proceedings of the 1997 13th Annual Symposium on Computational Geometry - Nice, Fr Duration: Jun 4 1997 → Jun 6 1997 |

### Other

Other | Proceedings of the 1997 13th Annual Symposium on Computational Geometry |
---|---|

City | Nice, Fr |

Period | 6/4/97 → 6/6/97 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics