Approximation algorithms for geometric shortest path problems
Lyudmil Aleksandrov, Anil Maheshwari, Jörg-Rüdiger Sack · 2000
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: O n 1 1 runs in (~ log ; (~ +log n)) time.The run time improves to O(;~-log ~logn)) when all weights are equal.This can be used to solve the shortest path problem amidst obstacles in 3-dimensional Euclidean space (ESP-3D).