Approximate Euclidean Shortest Paths in 3-Space

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.