2000 · 74 citations · 18 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryTheory Of ComputationAlgorithm AnalysisApproximation AlgorithmsComputational ComplexityGeometric ApproximationShortest Path AlgorithmsApproximation Algorithms For Shortest PathsShortest Path Problems
We consider the classical geometric problem of determining a shortest path through a weighted domain. We present approximation algorithms that compute e-short paths, i.e., paths whose costs are within a factor of 1 + e of the shortest path costs, for an arbitrary constant e > O, for the following geometric configurations:
18
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
New lower bound techniques for robot motion planning problems
John Canny, John H. Reif · 1987 · 544 citations
Joseph S. B. Mitchell, Christos H. Papadimitriou · Journal of the ACM · 1991 · 297 citations · Full text
Approximation algorithms for shortest path motion planning
Kenneth L. Clarkson · 1987 · 262 citations · Full text