Approximate euclidean shortest paths in 3-space

Joonsoo Choi, Juergen Sellen, Chee Keng Yap

Research output: Contribution to journalArticle

Abstract

Papadimitriou's approximation approach to the Euclidean shortest path (ESP) in 3-space is revisited. As this problem is NP-hard, his approach represents an important step towards practical algorithms. However, there are several gaps in the original description. Besides giving a complete treatment in the framework of bit complexity, we also improve on his subdivision method. Among the tools needed are root-separation bounds and nontrivial applications of Brent's complexity bounds on evaluation of elementary functions using floating point numbers.

Original languageEnglish (US)
Pages (from-to)271-295
Number of pages25
JournalInternational Journal of Computational Geometry and Applications
Volume7
Issue number4
DOIs
StatePublished - 1997

Keywords

  • Approximate euclidean shortest path
  • Exact geometric computation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Approximate euclidean shortest paths in 3-space'. Together they form a unique fingerprint.

  • Cite this