TY - JOUR
T1 - On finding approximate optimal paths in weighted regions
AU - Sun, Zheng
AU - Reif, John H.
N1 - Funding Information:
✩ Parts of this work were published in Proceedings of the 4th Workshop on Foundations of Algorithmic Robotics, 2000, pp. 191–203, and in Proceedings of the 14th International Symposium on Fundamentals of Computation Theory, in: Lecture Notes in Comput. Sci., vol. 2751, 2003, pp. 258–270. * Corresponding author. E-mail addresses: [email protected] (Z. Sun), [email protected] (J.H. Reif). 1 Supported in part by Hong Kong RGC Grant HKBU2107/04E. 2 Supported in part by NSF ITR Grants EIA-0086015 and 0326157, NSF QuBIC Grants EIA-0218376 and EIA-0218359, and DARPA/AFSOR Contract F30602-01-2-0561.
Publisher copyright:
© 2004 Elsevier Inc. All rights reserved.
PY - 2006/1
Y1 - 2006/1
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - Computational geometry
KW - Optimal paths
KW - Robotics
UR - http://www.scopus.com/inward/record.url?scp=28444473064&partnerID=8YFLogxK
U2 - 10.1016/j.jalgor.2004.07.004
DO - 10.1016/j.jalgor.2004.07.004
M3 - Journal article
AN - SCOPUS:28444473064
SN - 0196-6774
VL - 58
SP - 1
EP - 32
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -