More Web Proxy on the site http://driver.im/

research-article

Computing $$L_1$$ Shortest Paths Among Polygonal Obstacles in the Plane

Authors:

Haitao WangAuthors Info & Claims

Volume 81, Issue 6

Pages 2430 - 2483

https://doi.org/10.1007/s00453-018-00540-x

Published: 01 June 2019 Publication History

Abstract

Given a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, suppose a triangulation of the space outside the obstacles is given; we present an $$O(n+h\log h)$$ time and O(n) space algorithm for building a data structure (called shortest path map) of size O(n) such that for any query point t, the length of an $$L_1$$ shortest obstacle-avoiding path from s to t can be computed in $$O(\log n)$$ time and the actual path can be reported in additional time proportional to the number of edges of the path. The previously best algorithm computes such a shortest path map in $$O(n\log n)$$ time and O(n) space. So our algorithm is faster when h is relatively small. Further, our techniques can be extended to obtain improved results for other related problems, e.g., computing the $$L_1$$ geodesic Voronoi diagram for a set of point sites among the obstacles.

References

[1]

Atallah, M.J., Chen, D.Z., Wagener, H.: An optimal parallel algorithm for the visibility of a simple polygon from a point. J. ACM 38(3), 516–533 (1991)

[2]

Bar-Yehuda, R., Chazelle, B.: Triangulating disjoint Jordan chains. Int. J. Comput. Geom. Appl. 4(4), 475–481 (1994)

[3]

Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6, 485–524 (1991)

Digital Library

[4]

Chazelle, B., Edelsbrunner, H., Grigni, M., Gribas, L., Hershberger, J., Sharir, M., Snoeyink, J.: Ray shooting in polygons using geodesic triangulations. Algorithmica 12(1), 54–68 (1994)

[5]

Chazelle, B., Guibas, L.: Visibility and intersection problems in plane geometry. Discrete Comput. Geom. 4, 551–589 (1989)

Digital Library

[6]

Chen, D.Z., Hershberger, J., Wang, H.: Computing shortest paths amid convex pseudodisks. SIAM J. Comput. 42(3), 1158–1184 (2013)

[7]

Chen, D.Z., Inkulu, R., Wang, H.: Two-point $$L_1$$ shortest path queries in the plane. J. Comput. Geom. 1, 473–519 (2016)

[8]

Chen, D.Z., Klenk, K.S., Tu, H.-Y.T.: Shortest path queries among weighted obstacles in the rectilinear plane. SIAM J. Comput. 29(4), 1223–1246 (2000)

Digital Library

[9]

Chen, D.Z., Wang, H.: Computing the visibility polygon of an island in a polygonal domain. In: Proceedings of the 39th International Colloquium on Automata, Languages and Programming, pp. 218–229 (2012)

[10]

Chen, D.Z., Wang, H.: Computing shortest paths among curved obstacles in the plane. ACM Trans. Algorithms, 11, Article No. 26 (2015)

[11]

Clarkson, K., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in $$O(n \log ^2 n)$$ time. In: Proceedings of the 3rd Annual Symposium on Computational Geometry, pp. 251–257 (1987)

[12]

Clarkson, K., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in $$O(n \log ^{2/3} n)$$ time. Manuscript (1988)

[13]

de Rezende, P.J., Lee, D.T., Wu, Y.F.: Rectilinear shortest paths in the presence of rectangular barriers. Discrete Comput. Geom. 4, 41–53 (1989)

Digital Library

[14]

Edelsbrunner, H., Guibas, L., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317–340 (1986)

Digital Library

[15]

Ghosh, S.K., Mount, D.M.: An output-sensitive algorithm for computing visibility graphs. SIAM J. Comput. 20(5), 888–910 (1991)

Digital Library

[16]

Guibas, L., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2(1–4), 209–233 (1987)

Digital Library

[17]

Hershberger, J., Snoeyink, J.: Computing minimum length paths of a given homotopy class. Comput. Geom. 4(2), 63–97 (1994)

Digital Library

[18]

Hershberger, J., Suri, S.: A pedestrian approach to ray shooting: shoot a ray, take a walk. J. Algorithms 18(3), 403–431 (1995)

Digital Library

[19]

Hershberger, J., Suri, S.: An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput. 28(6), 2215–2256 (1999)

Digital Library

[20]

Hertel, S., Mehlhorn, K.: Fast triangulation of the plane with respect to simple polygons. Inf. Control 64, 52–76 (1985)

Digital Library

[21]

Inkulu, R., Kapoor, S.: Planar rectilinear shortest path computation using corridors. Comput. Geom. 42(9), 873–884 (2009)

Digital Library

[22]

Inkulu, R., Kapoor, S., Maheshwari, S.N.: A near optimal algorithm for finding Euclidean shortest path in polygonal domain. arXiv:1011.6481v1 (2010)

[23]

Joe, B., Simpson, R.B.: Corrections to Lee’s visibility polygon algorithm. BIT 27, 458–473 (1987)

Digital Library

[24]

Kapoor, S., Maheshwari, S.N.: Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In: Proceedings of the 4th Annual ACM Symposium on Computational Geometry, pp. 172–182 (1988)

[25]

Kapoor, S., Maheshwari, S.N., Mitchell, J.S.B.: An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete Comput. Geom. 18(4), 377–383 (1997)

[26]

Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM J. Comput. 12(1), 28–35 (1983)

Digital Library

[27]

Larson, R.C., Li, V.O.K.: Finding minimum rectilinear distance paths in the presence of barriers. Networks 11, 285–304 (1981)

[28]

Lee, D.T.: Visibility of a simple polygon. Comput. Vis. Graph. Image Process. 22(2), 207–221 (1983)

[29]

Mitchell, J.S.B.: An optimal algorithm for shortest rectilinear paths among obstacles. In: Abstracts of the 1st Canadian Conference on Computational Geometry (1989)

[30]

Mitchell, J.S.B.: $$L_1$$ shortest paths among polygonal obstacles in the plane. Algorithmica 8(1), 55–88 (1992)

Digital Library

[31]

Mitchell, J.S.B.: Shortest paths among obstacles in the plane. Int. J. Comput. Geom. Appl. 6(3), 309–332 (1996)

[32]

Oh, E., Ahn, H.-K.: Voronoi diagrams for a moderate-sized point-set in a simple polygon. In: Proceedings of the 33rd International Symposium on Computational Geometry, pp. 52:1–52:15 (2017)

[33]

Papadopoulou, E., Lee, D.T.: A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains. Algorithmica 20, 319–352 (1998)

[34]

Rohnert, H.: Shortest paths in the plane with convex polygonal obstacles. Inf. Process. Lett. 23(2), 71–76 (1986)

Digital Library

[35]

Shamos, M.I., Hoey, D.: Closest-point problems. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pp. 151–162 (1975)

[36]

Storer, J.A., Reif, J.H.: Shortest paths in the plane with polygonal obstacles. J. ACM 41(5), 982–1012 (1994)

Digital Library

[37]

Widmayer, P.: On graphs preserving rectilinear shortest paths in the presence of obstacles. Ann. Oper. Res. 33(7), 557–575 (1991)

[38]

Widmayer, P., Wu, Y.F., Wong, C.K.: On some distance problems in fixed orientations. SIAM J. Comput. 16(4), 728–746 (1987)

Digital Library

Cited By

Wang H(2023)A New Algorithm for Euclidean Shortest Paths in the PlaneJournal of the ACM10.1145/358047570:2(1-62)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3580475
Wang HKhuller SVassilevska Williams V(2021)A new algorithm for Euclidean shortest paths in the planeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451037(975-988)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451037
Wang H(2019)Bicriteria Rectilinear Shortest Paths Among Rectilinear Obstacles in the PlaneDiscrete & Computational Geometry10.1007/s00454-019-00112-y62:3(525-582)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s00454-019-00112-y

Index Terms

Computing $$L_1$$ Shortest Paths Among Polygonal Obstacles in the Plane

Index terms have been assigned to the content through auto-classification.

Recommendations

Computing Shortest Paths among Curved Obstacles in the Plane

A fundamental problem in computational geometry is to compute an obstacle-avoiding Euclidean shortest path between two points in the plane. The case of this problem on polygonal obstacles is well studied. In this article, we consider the problem version ...
Computing shortest paths among curved obstacles in the plane
SoCG '13: Proceedings of the twenty-ninth annual symposium on Computational geometry

In this paper, we study the problem of finding Euclidean shortest paths among curved obstacles in the plane. We model curved obstacles as splinegons. A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge, and each curved ...
Two-Point L1 Shortest Path Queries in the Plane
SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

Let P be a set of h pairwise-disjoint polygonal obstacles with a total of n vertices in the plane. In this paper, we consider the problem of building a data structure that can quickly compute an L1 shortest obstacle-avoiding path between any two query ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 81, Issue 6

Jun 2019

530 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © 2019 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 2019

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang H(2023)A New Algorithm for Euclidean Shortest Paths in the PlaneJournal of the ACM10.1145/358047570:2(1-62)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3580475
Wang HKhuller SVassilevska Williams V(2021)A new algorithm for Euclidean shortest paths in the planeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451037(975-988)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451037
Wang H(2019)Bicriteria Rectilinear Shortest Paths Among Rectilinear Obstacles in the PlaneDiscrete & Computational Geometry10.1007/s00454-019-00112-y62:3(525-582)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s00454-019-00112-y

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents