Abstract
Given a set of h pairwise disjoint polygonal obstacles of totally n vertices in the plane, we study the problem of computing an L 1 (or rectilinear) shortest path between two points avoiding the obstacles. Previously, this problem has been solved in O(nlogn) time and O(n) space, or alternatively in O(n + hlog1.5 n) time and O(n + hlog1.5 h) space. A lower bound of Ω(n + hlogh) time and Ω(n) space can be established for this problem. In this paper, we present a nearly optimal algorithm of O(n + hlog1 + ε h) time and O(n) space for the problem, where ε > 0 is an arbitrarily small constant. Specifically, after the free space is triangulated in O(n + hlog1 + ε h) time, our algorithm finds a shortest path in O(n + hlogh) time and O(n) space. Our algorithm can also be extended to obtain improved results for other related problems, e.g., finding shortest paths with fixed orientations, finding approximate Euclidean shortest paths, etc. In addition, our techniques yield improved results on some shortest path query problems.
This research was supported in part by NSF under Grant CCF-0916606.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bar-Yehuda, R., Chazelle, B.: Triangulating disjoint Jordan chains. International Journal of Computational Geometry and Applications 4(4), 475–481 (1994)
Chazelle, B.: Triangulating a simple polygon in linear time. Discrete and Computational Geometry 6, 485–524 (1991)
Chen, D., Klenk, K., Tu, H.Y.: Shortest path queries among weighted obstacles in the rectilinear plane. SIAM Journal on Computing 29(4), 1223–1246 (2000)
Chen, D., Wang, H.: Computing shortest paths among curved obstacles in the plane. In: arXiv:1103.3911 (2011)
Clarkson, K.: Approximation algorithms for shortest path motion planning. In: Proc. of the 19th Annual ACM Symposium on Theory of Computing, pp. 56–65 (1987)
Clarkson, K., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in O(n log2 n) time. In: Proc. of the 3rd Annual Symposium on Computational Geometry, pp. 251–257 (1987)
Clarkson, K., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in O(n log2/3 n) time (1988) (manuscript)
Edelsbrunner, H., Guibas, L., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM Journal on Computing 15(2), 317–340 (1986)
Ghosh, S., Mount, D.: An output-sensitive algorithm for computing visibility. SIAM Journal on Computing 20(5), 888–910 (1991)
Hershberger, J., Snoeyink, J.: Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications 4(2), 63–97 (1994)
Hershberger, J., Suri, S.: An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on Computing 28(6), 2215–2256 (1999)
Hertel, S., Mehlhorn, K.: Fast triangulation of the plane with respect to simple polygons. Information and Control 64, 52–76 (1985)
Inkulu, R., Kapoor, S.: Planar rectilinear shortest path computation using corridors. Computational Geometry: Theory and Applications 42(9), 873–884 (2009)
Inkulu, R., Kapoor, S., Maheshwari, S.: A near optimal algorithm for finding Euclidean shortest path in polygonal domain. In: arXiv:1011.6481v1 (2010)
Kapoor, S., Maheshwari, S., Mitchell, J.: An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete and Computational Geometry 18(4), 377–383 (1997)
Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM Journal on Computing 12(1), 28–35 (1983)
Larsona, R., Li, V.: Finding minimum rectilinear distance paths in the presence of barriers. Networks 11, 285–304 (1981)
Mitchell, J.: An optimal algorithm for shortest rectilinear paths among obstacles. In: Abstracts of the 1st Canadian Conference on Computational Geometry (1989)
Mitchell, J.: L 1 shortest paths among polygonal obstacles in the plane. Algorithmica 8(1), 55–88 (1992)
Mitchell, J.: Shortest paths among obstacles in the plane. International Journal of Computational Geometry and Applications 6(3), 309–332 (1996)
de Rezende, P., Lee, D., Wu, Y.: Rectilinear shortest paths with rectangular barriers. In: Proc. of the 1st Annual Symposium on Computational Geometry, pp. 204–213 (1985)
Storer, J., Reif, J.: Shortest paths in the plane with polygonal obstacles. Journal of the ACM 41(5), 982–1012 (1994)
Widmayer, P.: On graphs preserving rectilinear shortest paths in the presence of obstacles. Annals of Operations Research 33(7), 557–575 (1991)
Widmayer, P., Wu, Y., Wong, C.: On some distance problems in fixed orientations. SIAM Journal on Computing 16(4), 728–746 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, D.Z., Wang, H. (2011). A Nearly Optimal Algorithm for Finding L 1 Shortest Paths among Polygonal Obstacles in the Plane. In: Demetrescu, C., Halldórsson, M.M. (eds) Algorithms – ESA 2011. ESA 2011. Lecture Notes in Computer Science, vol 6942. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23719-5_41
Download citation
DOI: https://doi.org/10.1007/978-3-642-23719-5_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23718-8
Online ISBN: 978-3-642-23719-5
eBook Packages: Computer ScienceComputer Science (R0)