International Journal of Computational Geometry & Applications · 1997 · 42 citations · 0 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryGeometryAlgorithm AnalysisApproximation AlgorithmsComputational ComplexityGeometric ApproximationShortest Path AlgorithmsApproximation Algorithms For Shortest PathsApproximation HardnessComplexityRoot SeparationShortest Euclidean PathShortest Path ProblemsShortest PathsSubdivision
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 nontrivial applications of Brent's complexity bounds on evaluation of elementary functions using floating point numbers.