Approximation algorithms for geometric shortest path problems
We consider the classical geometric problem of determining a shortest path through a weighted domain. We present approximation algorithms that compute ε-short paths, i.e., paths whose costs are within a factor of 1 + ε of the shortest path costs, for an arbitrary constant ε > O, for the following geometric configurations: SPPS Problem: We are given a polyhedron P consisting of n convex faces and each face has a positive non-zero real valued weight. The shortest path on polyhedral surface problem (SPPS) is to compute a path of least cost that remains on the surface of P between any two vertices, where the cost of the path is defined to be the weighted sum of Euclidean lengths of the sub-paths within each face. Our algorithm runs in O(n/ε log 1/ε (1/√ε + log n)) time for 0 < ε < 1. The run time improves to O(n log n) for ε ≥ 1 and to O(n/ε log 1/ε log n) when all weights are equal.
|Conference||32nd Annual ACM Symposium on Theory of Computing, STOC 2000|
Aleksandrov, L. (Lyudmil), Maheshwari, A, & Sack, J.-R. (2000). Approximation algorithms for geometric shortest path problems. In Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 286–295). doi:10.1145/335305.335339