Approximation algorithms for geometric shortest path problems
The classical geometric problem of determining a shortest path through a weighted domain is considered. Approximation algorithms are presented to compute ε-short paths, that is paths whose costs are within a factor of 1+ε of the shortest path costs for an arbitrary constant ε>0, for some geometric configurations.
|Conference||32nd Annual ACM Symposium on Theory of Computing|
Aleksandrov, L. (Lyudmil), Maheshwari, A, & Sack, J.-R. (2000). Approximation algorithms for geometric shortest path problems. Presented at the 32nd Annual ACM Symposium on Theory of Computing.