Carleton University
Technical Report TR-99-10
October 1999
Approximation Algorithms for Geometric Shortest Path Problems
L. Aleksandrov, A. Maheshwari, J.R. Sack
Abstract
We consider the classical geometric problem of determining shortest path through a weighted domain. We p[resent 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 > 0, for geometric configurations.