Approximating shortest paths on a convex polytope in three dimensions

Sariel Har-Peled, Micha Sharir, Kasturi R. Varadarajan

Research output: Contribution to conferencePaperpeer-review

Abstract

We present an approximation algorithm that, given a convex polytope P with n faces in R3, points s, t ε ∂P, and a parameter 0 < ε ≤ 1, constructs a path on ∂P from s to t whose length is at most (1 + ε)dP(s, t), where dP(s, t) is the length of the shortest path between s and t on ∂P. The algorithm runs in O(n · min {1/ε1.5, log n} + 1/ε4.5 log(1/ε)) time, and is relatively simple to implement. We also present an extension of the algorithm that computes approximate shortest paths from a given source point on ∂P to all vertices of P.

Original languageEnglish (US)
Pages329-338
Number of pages10
DOIs
StatePublished - 1996
Externally publishedYes
EventProceedings of the 1996 12th Annual Symposium on Computational Geometry - Philadelphia, PA, USA
Duration: May 24 1996May 26 1996

Other

OtherProceedings of the 1996 12th Annual Symposium on Computational Geometry
CityPhiladelphia, PA, USA
Period5/24/965/26/96

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Approximating shortest paths on a convex polytope in three dimensions'. Together they form a unique fingerprint.

Cite this