@inproceedings{a0c1b6984469465bae0211fdda3d2ec4,

title = "Approximate Euclidean shortest path in 3-space",

abstract = "Papadimitriou's approximation approach to the Euclidean shortest path (ESP) problem in 3-space is revisited. As this problem is NP-hard, his approach represents an important step towards practical algorithms. Unfortunately, there are non-trivial gaps in the original description. Besides giving a complete treatment, we also give an alternative to his subdivision method which has some nice properties. 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.",

author = "Joonsoo Choi and Jurgen Sellen and Yap, {Chee Keng}",

year = "1994",

doi = "10.1145/177424.177501",

language = "English (US)",

isbn = "0897916484",

series = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "Publ by ACM",

pages = "41--48",

booktitle = "Proceedings of the Annual Symposium on Computational Geometry",

note = "Proceedings of the 10th Annual Symposium on Computational Geometry ; Conference date: 06-06-1994 Through 08-06-1994",

}