## On finding approximate optimal paths in weighted regions

The main result of this paper is an approximation algorithm for the weighted region optimal path problem. In this problem, a point robot moves in a planar space composed of n triangular regions, each of which is associated with a positive unit weight. The objective is to find, for given source and destination points s and t, a path from s to t with the minimum weighted length. Our algorithm, BUSHWHACK, adopts a traditional approach (see [M. Lanthier, A. Maheshwari, J.-R. Sack, Approximating weighted shortest paths on polyhedral surfaces, in: Proceedings of the 13th Annual ACM Symposium on Coputational Geometry, 1997, pp. 274-283; L. Aleksandrov, M. Lanthier, A. Maheshwari, J.-R. Sack, An ε-approximation algorithm for weighted shortest paths on polyhedral surfaces, in: Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, in: Lecture Notes in Comput. Sci., vol. 1432, 1998, pp. 11-22; L. Aleksandrov, A. Maheshwari, J.-R. Sack, Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286-295]) that converts the original continuous geometric search space into a discrete graph G by placing representative points on boundary edges. However, by exploiting geometric structures that we call intervals, BUSHWHACK computes an approximate optimal path more efficiently as it accesses only a sparse subgraph of G. Combined with the logarithmic discretization scheme introduced by Aleksandrov et al. [Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286-295], BUSHWHACK can compute an ε-approximation in O(nε(log1ε+logn) log1ε) time. By reducing complexity dependency on ε, this result improves on all previous results with the same discretization approach. We also provide an improvement over the discretization scheme of [L. Aleksandrov, A. Maheshwari, J.-R. Sack, Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286-295] so that the size of G is no longer dependent on unit weight ratio, the ratio between the maximum and minimum unit weights. This leads to the first ε-approximation algorithm whose time complexity does not depend on unit weight ratio. © 2004 Elsevier Inc. All rights reserved.

### Duke Scholars

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 0802 Computation Theory and Mathematics

### Citation

*Journal of Algorithms*,

*58*(1), 1–32. https://doi.org/10.1016/j.jalgor.2004.07.004

*Journal of Algorithms*58, no. 1 (January 1, 2006): 1–32. https://doi.org/10.1016/j.jalgor.2004.07.004.

*Journal of Algorithms*, vol. 58, no. 1, Jan. 2006, pp. 1–32.

*Scopus*, doi:10.1016/j.jalgor.2004.07.004.

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 0802 Computation Theory and Mathematics