Approximate Euclidean Shortest Path in 3-Space

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 non-trivial applications of Brent's complexity bounds on evaluation of elementary functions using floating point numbers. 1 Introduction The Euclidean shortest path (ESP) problem can be formulated as follows: given a collection of polyhedral obstacles in physical space S, and source and target points s 0 ; t 0 2 S, find a shortest obstacle-avoiding path between s 0 and t 0 . Here S is typically E 2 or E 3 . It is evident that this is a basic problem in applications such as robotics. The case S = E 2 has recently seen a major breakthrough, with the O(..