TY - GEN

T1 - Precision-sensitive Euclidean shortest path in 3-space

AU - Choi, Joonsoo

AU - Sellen, Jürgen

AU - Yap, Chee Keng

N1 - Funding Information:
*Work on this paper by Sellen has been supported by a postdoctoral fellowship from the DAAD, Germany. Choi and Yap are supported by NSF grant #CCR-9402464.
Publisher Copyright:
© 1995 ACM.

PY - 1995/9/1

Y1 - 1995/9/1

N2 - This paper introduces the concept of precision-sensitive algorithms, in analogy to the well-known output-sensitive algorithms. We exploit this idea in studying the complexity of the 3-dimensional Euclidean shortest path problem. Specifically, we analyze an incremental approximation approach based on ideas in [CSY], and show that this approach yields an asymptotic improvement of running time. By using an optimization technique to improve paths on fixed edge sequences, we modify this algorithm to guarantee a relative error of 0(2-r) in a time polynomial in r and 1/6, where 6 denotes the relative difference in path length between the shortest and the second shortest path. Our result is the best possible in some sense: if we have a strongly precision-sensitive algorithm then we can show that USAT (unambiguous SAT) is in polynomial time, which is widely conjectured to be unlikely. Finally, we discuss the practicability of this approach. Experimental results are provided.

AB - This paper introduces the concept of precision-sensitive algorithms, in analogy to the well-known output-sensitive algorithms. We exploit this idea in studying the complexity of the 3-dimensional Euclidean shortest path problem. Specifically, we analyze an incremental approximation approach based on ideas in [CSY], and show that this approach yields an asymptotic improvement of running time. By using an optimization technique to improve paths on fixed edge sequences, we modify this algorithm to guarantee a relative error of 0(2-r) in a time polynomial in r and 1/6, where 6 denotes the relative difference in path length between the shortest and the second shortest path. Our result is the best possible in some sense: if we have a strongly precision-sensitive algorithm then we can show that USAT (unambiguous SAT) is in polynomial time, which is widely conjectured to be unlikely. Finally, we discuss the practicability of this approach. Experimental results are provided.

UR - http://www.scopus.com/inward/record.url?scp=85010084001&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85010084001&partnerID=8YFLogxK

U2 - 10.1145/220279.220317

DO - 10.1145/220279.220317

M3 - Conference contribution

AN - SCOPUS:85010084001

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 350

EP - 359

BT - Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995

PB - Association for Computing Machinery

T2 - 11th Annual Symposium on Computational Geometry, SCG 1995

Y2 - 5 June 1995 through 7 June 1995

ER -