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.

Additional Metadata
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.