Precision-sensitive Euclidean shortest path in 3-space

Joonsoo Choi, Jürgen Sellen, Chee Keng Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper introduces the concept of precision-sensitive algorithms, in analogy to the well-known output-sensitive algorithms. We exploit this idea in studying the complexity of the 3-dimensional Euclidean shortest path problem. Specifically, we analyze an incremental approximation approach based on ideas in [CSY], and show that this approach yields an asymptotic improvement of running time. By using an optimization technique to improve paths on fixed edge sequences, we modify this algorithm to guarantee a relative error of 0(2-r) in a time polynomial in r and 1/6, where 6 denotes the relative difference in path length between the shortest and the second shortest path. Our result is the best possible in some sense: if we have a strongly precision-sensitive algorithm then we can show that USAT (unambiguous SAT) is in polynomial time, which is widely conjectured to be unlikely. Finally, we discuss the practicability of this approach. Experimental results are provided.

Original languageEnglish (US)
Title of host publicationProceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995
PublisherAssociation for Computing Machinery
Pages350-359
Number of pages10
ISBN (Electronic)0897917243
DOIs
StatePublished - Sep 1 1995
Event11th Annual Symposium on Computational Geometry, SCG 1995 - Vancouver, Canada
Duration: Jun 5 1995Jun 7 1995

Publication series

NameProceedings of the Annual Symposium on Computational Geometry
VolumePart F129372

Other

Other11th Annual Symposium on Computational Geometry, SCG 1995
CountryCanada
CityVancouver
Period6/5/956/7/95

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Precision-sensitive Euclidean shortest path in 3-space'. Together they form a unique fingerprint.

Cite this