Approximate Euclidean Shortest Paths in 3-Space
Joonsoo Choi, Juergen Sellen, Chee-Keng Yap · International Journal of Computational Geometry & Applications · 1997
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.