Precision-sensitive Euclidean shortest path in 3-space

Jürgen Sellen, Joonsoo Choi, Chee Keng Yap

Research output: Contribution to journalArticlepeer-review


This paper introduces the concept of precision-sensitive algorithms, analogous 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 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 O(2-r) in a time polynomial in r and 1/δ, where δ 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 unambiguous SAT (USAT) 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)
Pages (from-to)1577-1595
Number of pages19
JournalSIAM Journal on Computing
Issue number5
StatePublished - Mar 2000

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


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

Cite this