Precision-sensitive Euclidean shortest path in 3-space

This paper introduces the concept of precision-sensitive algorithms, analog ous to the well-known output-sensitive algorithms. We exploit this idea in studying the complexity of the 3-dimensional Euclidean shortest path proble m. Specifically, we analyze an incremental approximation approach and show that this approach yields an asymptotic improvement of running time. By usi ng an optimization technique to improve paths on fixed edge sequences, we m odify this algorithm to guarantee a relative error of O(2(-r)) in a time po lynomial in r and 1/delta, where delta denotes the relative difference in p ath length between the shortest and the second shortest path. Our result is the best possible in some sense: if we have a strongly precis ion-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 resul ts are provided.