On finding approximate optimal paths in weighted regions

Zheng Sun*, John H. Reif

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

45 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)1-32
Number of pages32
JournalJournal of Algorithms
Volume58
Issue number1
DOIs
Publication statusPublished - Jan 2006
Externally publishedYes

Scopus Subject Areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

User-Defined Keywords

  • Approximation algorithms
  • Computational geometry
  • Optimal paths
  • Robotics

Fingerprint

Dive into the research topics of 'On finding approximate optimal paths in weighted regions'. Together they form a unique fingerprint.

Cite this