1994 · 78 citations · 6 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryGeometryAlgorithm AnalysisApproximation AlgorithmsComputational ComplexityGeometric ApproximationShortest Path AlgorithmsApproximation Algorithms For Shortest PathsApproximation HardnessRoot SeparationShortest Euclidean PathShortest Path ProblemsSubdivision
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.
6
New lower bound techniques for robot motion planning problems
John Canny, John H. Reif · 1987 · 544 citations
Fast Multiple-Precision Evaluation of Elementary Functions
Richard P. Brent · Journal of the ACM · 1976 · 371 citations · Full text
Approximation algorithms for shortest path motion planning
Kenneth L. Clarkson · 1987 · 262 citations · Full text
Harry Lass, M. J. Walker · American Journal of Physics · 1950 · 150 citations