A new algorithm for Euclidean shortest paths in the plane. (English) Zbl 07765225
Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 975-988 (2021).
MSC:
| 68Qxx | Theory of computing |
Keywords:
Euclidean distance; obstacle avoidance; polygonal domain; shortest path; shortest path map; shortest path queryReferences:
| [1] | S.W. Bae and H. Wang. 2019. L_1 shortest path queries in simple polygons. Theoretical Computer Science, 790, 2019. Pages 105-116. · Zbl 1430.68354 |
| [2] | R. Bar-Yehuda and B. Chazelle. 1994. Triangulating disjoint Jordan chains. International Journal of Computational Geometry and Applications, 4, 4, 1994. Pages 475-481. · Zbl 0829.68124 |
| [3] | D.Z. Chen, J. Hershberger, and H. Wang. 2013. Computing shortest paths amid convex pseudodisks. SIAM J. Comput., 42, 3, 2013. Pages 1158-1184. · Zbl 1275.68076 |
| [4] | D.Z. Chen, R. Inkulu, and H. Wang. 2016. Two-point L_1 shortest path queries in the plane. Journal of Computational Geometry, 1, 2016. Pages 473-519. · Zbl 1405.68098 |
| [5] | D.Z. Chen, K.S. Klenk, and H.-Y.T. Tu. 2000. Shortest path queries among weighted obstacles in the rectilinear plane. SIAM J. Comput., 29, 4, 2000. Pages 1223-1246. · Zbl 0947.68073 |
| [6] | D.Z. Chen and H. Wang. 2015. Computing shortest paths among curved obstacles in the plane. ACM Transactions on Algorithms, 11, 2015. · Zbl 1398.68617 |
| [7] | D.Z. Chen and H. Wang. 2015. A new algorithm for computing visibility graphs of polygonal obstacles in the plane. Journal of Computational Geometry, 6, 2015. Pages 316-345. · Zbl 1405.68409 |
| [8] | D.Z. Chen and H. Wang. 2017. Computing the visibility polygon of an island in a polygonal domain. Algorithmica, 77, 2017. Pages 40-64. · Zbl 1364.68343 |
| [9] | D.Z. Chen and H. Wang. 2019. Computing L_1 shortest paths among polygonal obstacles in the plane.. Algorithmica, 81, 2019. Pages 2430-2483. · Zbl 1421.68164 |
| [10] | Y.-J. Chiang and J.S.B. Mitchell. 1999. Two-point Euclidean shortest path queries in the plane. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 215-224. · Zbl 0938.68132 |
| [11] | K.L. Clarkson, R. Cole, and R.E. Tarjan. 1992. Randomized parallel algorithms for trapezoidal diagrams. International Journal of Computational Geometry and Application, 2, 1992. Pages 117-133. · Zbl 0762.68062 |
| [12] | K. Clarkson, S. Kapoor, and P. Vaidya. 1987. Rectilinear shortest paths through polygonal obstacles in O(n \qopname \relax olog^2 n) time. In Proceedings of the 3rd Annual Symposium on Computational Geometry (SoCG). Pages 251-257. |
| [13] | K. Clarkson, S. Kapoor, and P. Vaidya. 1988. Rectilinear shortest paths through polygonal obstacles in O(n \qopname \relax olog^2/3 n) time. Manuscript. |
| [14] | P.J. de Rezende, D.T. Lee, and Y.F. Wu. 1989. Rectilinear shortest paths in the presence of rectangular barriers. Discrete and Computational Geometry, 4, 1989. Pages 41-53. · Zbl 0655.05041 |
| [15] | E.D. Demaine, J.S.B. Mitchell, and J. O’Rourke. 2020. The open problem project. |
| [16] | H. Edelsbrunner, L. Guibas, and J. Stolfi. 1986. Optimal point location in a monotone subdivision. SIAM J. Comput., 15, 2, 1986. Pages 317-340. · Zbl 0602.68102 |
| [17] | S.D. Eriksson-Bique, J. Hershberger, V. Polishchuk, B. Speckmann, S. Suri, T. Talvitie, K. Verbeek, and H. Y\i ld\i z. 2015. Geometric k shortest paths. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1616-1625. · Zbl 1371.68292 |
| [18] | S.K. Ghosh and D.M. Mount. 1991. An output-sensitive algorithm for computing visibility graphs. SIAM J. Comput., 20, 5, 1991. Pages 888-910. · Zbl 0768.68202 |
| [19] | L.J. Guibas and J. Hershberger. 1989. Optimal shortest path queries in a simple polygon. J. Comput. System Sci., 39, 2, 1989. Pages 126-152. · Zbl 0681.68065 |
| [20] | L.J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R.E. Tarjan. 1987. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2, 1-4, 1987. Pages 209-233. · Zbl 0642.68081 |
| [21] | J. Hershberger. 1991. A new data structure for shortest path queries in a simple polygon. Inform. Process. Lett., 38, 5, 1991. Pages 231-235. · Zbl 0738.68021 |
| [22] | J. Hershberger and J. Snoeyink. 1994. Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications, 4, 1994. Pages 63-97. · Zbl 0815.68116 |
| [23] | J. Hershberger and S. Suri. 1999. An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput., 28, 1999. Pages 2215-2256. · Zbl 0939.68157 |
| [24] | J. Hershberger, S. Suri, and H. Y\i ld\i z. 2013. A near-optimal algorithm for shortest paths among curved obstacles in the plane. In Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG). Pages 359-368. · Zbl 1305.68239 |
| [25] | S. Hertel and K. Mehlhorn. 1985. Fast triangulation of the plane with respect to simple polygons. Information and Control, 64, 1985. Pages 52-76. · Zbl 0575.68049 |
| [26] | R. Inkulu, S. Kapoor, and S.N. Maheshwari. 2010. A near optimal algorithm for finding Euclidean shortest path in polygonal domain. In arXiv:1011.6481v1. |
| [27] | S. Kapoor and S.N. Maheshwari. 1988. Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In Proceedings of 4th Annual ACM Symposium on Computational Geometry (SoCG). Pages 172-182. |
| [28] | S. Kapoor and S.N. Maheshwari. 2000. Efficiently constructing the visibility graph of a simple polygon with obstacles. SIAM J. Comput., 30, 3, 2000. Pages 847-871. · Zbl 0966.68081 |
| [29] | S. Kapoor, S.N. Maheshwari, and J.S.B. Mitchell. 1997. An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete and Computational Geometry, 18, 1997. Pages 377-383. · Zbl 0892.68047 |
| [30] | D. Kirkpatrick. 1983. Optimal search in planar subdivisions. SIAM J. Comput., 12, 1983. Pages 28-35. · Zbl 0501.68034 |
| [31] | D. Kirkpatrick and J. Snoeyink. 1995. Tentative prune-and-search for computing fixed-points with applications to geometric computation. Fundamenta Informaticae, 22, 1995. Pages 353-370. · Zbl 0815.68119 |
| [32] | D.T. Lee and F.P. Preparata. 1984. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14, 1984. Pages 393-410. · Zbl 0545.90098 |
| [33] | J.S.B. Mitchell. 1989. An optimal algorithm for shortest rectilinear paths among obstacles. Abstracts of the \em 1st Canadian Conference on Computational Geometry. |
| [34] | J.S.B. Mitchell. 1991. A new algorithm for shortest paths among obstacles in the plane. Annals of Mathematics and Artificial Intelligence, 3, 1991. Pages 83-105. · Zbl 0875.68765 |
| [35] | J.S.B. Mitchell. 1992. L_1 shortest paths among polygonal obstacles in the plane. Algorithmica, 8, 1992. Pages 55-88. · Zbl 0753.68093 |
| [36] | J.S.B. Mitchell. 1996. Shortest paths among obstacles in the plane. International Journal of Computational Geometry and Applications, 6, 1996. Pages 309-332. · Zbl 0860.68109 |
| [37] | J.S.B. Mitchell and S. Suri. 1995. Separation and approximation of polyhedral objects. Computational Geometry: Theory and Applications, 5, 1995. Pages 95-114. · Zbl 0831.68113 |
| [38] | M. Overmars and J. van Leeuwen.. 1981. Maintenance of configurations in the plane. J. Comput. System Sci., 23, 1981. Pages 166-204. · Zbl 0474.68082 |
| [39] | H. Rohnert. 1986. Shortest paths in the plane with convex polygonal obstacles. Inform. Process. Lett., 23, 1986. Pages 71-76. · Zbl 0607.68052 |
| [40] | N. Sarnak and R.E. Tarjan. 1986. Planar point location using persistent search trees. Commun. ACM, 29, 1986. Pages 669-679. |
| [41] | M. Sharir and A. Schorr. 1986. On shortest paths in polyhedral spaces. SIAM J. Comput., 15, 1986. Pages 193-215. · Zbl 0612.68090 |
| [42] | J.A. Storer and J.H. Reif. 1994. Shortest paths in the plane with polygonal obstacles. J. ACM, 41, 1994. Pages 982-1012. · Zbl 0814.68129 |
| [43] | H. Wang. 2020. A divide-and-conquer algorithm for two-point L_1 shortest path queries in polygonal domains. Journal of Computational Geometry, 11, 2020. Pages 235-282. · Zbl 1477.68499 |
| [44] | H. Wang. 2021. Shortest paths among obstacles in the plane revisited. In Proceedings of the 32nd Annual Symposium on Discrete Algorithms (SODA). Pages 810-821. · Zbl 07788389 |
| [45] | S.W. Bae and H. Wang. 2019. L_1 shortest path queries in simple polygons. Theoretical Computer Science, 790, 2019. Pages 105-116. · Zbl 1430.68354 |
| [46] | R. Bar-Yehuda and B. Chazelle. 1994. Triangulating disjoint Jordan chains. International Journal of Computational Geometry and Applications, 4, 4, 1994. Pages 475-481. · Zbl 0829.68124 |
| [47] | D.Z. Chen, J. Hershberger, and H. Wang. 2013. Computing shortest paths amid convex pseudodisks. SIAM J. Comput., 42, 3, 2013. Pages 1158-1184. · Zbl 1275.68076 |
| [48] | D.Z. Chen, R. Inkulu, and H. Wang. 2016. Two-point L_1 shortest path queries in the plane. Journal of Computational Geometry, 1, 2016. Pages 473-519. · Zbl 1405.68098 |
| [49] | D.Z. Chen, K.S. Klenk, and H.-Y.T. Tu. 2000. Shortest path queries among weighted obstacles in the rectilinear plane. SIAM J. Comput., 29, 4, 2000. Pages 1223-1246. · Zbl 0947.68073 |
| [50] | D.Z. Chen and H. Wang. 2015. Computing shortest paths among curved obstacles in the plane. ACM Transactions on Algorithms, 11, 2015. · Zbl 1398.68617 |
| [51] | D.Z. Chen and H. Wang. 2015. A new algorithm for computing visibility graphs of polygonal obstacles in the plane. Journal of Computational Geometry, 6, 2015. Pages 316-345. · Zbl 1405.68409 |
| [52] | D.Z. Chen and H. Wang. 2017. Computing the visibility polygon of an island in a polygonal domain. Algorithmica, 77, 2017. Pages 40-64. · Zbl 1364.68343 |
| [53] | D.Z. Chen and H. Wang. 2019. Computing L_1 shortest paths among polygonal obstacles in the plane.. Algorithmica, 81, 2019. Pages 2430-2483. · Zbl 1421.68164 |
| [54] | Y.-J. Chiang and J.S.B. Mitchell. 1999. Two-point Euclidean shortest path queries in the plane. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 215-224. · Zbl 0938.68132 |
| [55] | K.L. Clarkson, R. Cole, and R.E. Tarjan. 1992. Randomized parallel algorithms for trapezoidal diagrams. International Journal of Computational Geometry and Application, 2, 1992. Pages 117-133. · Zbl 0762.68062 |
| [56] | K. Clarkson, S. Kapoor, and P. Vaidya. 1987. Rectilinear shortest paths through polygonal obstacles in O(n \qopname \relax olog^2 n) time. In Proceedings of the 3rd Annual Symposium on Computational Geometry (SoCG). Pages 251-257. |
| [57] | K. Clarkson, S. Kapoor, and P. Vaidya. 1988. Rectilinear shortest paths through polygonal obstacles in O(n \qopname \relax olog^2/3 n) time. Manuscript. |
| [58] | P.J. de Rezende, D.T. Lee, and Y.F. Wu. 1989. Rectilinear shortest paths in the presence of rectangular barriers. Discrete and Computational Geometry, 4, 1989. Pages 41-53. · Zbl 0655.05041 |
| [59] | E.D. Demaine, J.S.B. Mitchell, and J. O’Rourke. 2020. The open problem project. |
| [60] | H. Edelsbrunner, L. Guibas, and J. Stolfi. 1986. Optimal point location in a monotone subdivision. SIAM J. Comput., 15, 2, 1986. Pages 317-340. · Zbl 0602.68102 |
| [61] | S.D. Eriksson-Bique, J. Hershberger, V. Polishchuk, B. Speckmann, S. Suri, T. Talvitie, K. Verbeek, and H. Y\i ld\i z. 2015. Geometric k shortest paths. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1616-1625. · Zbl 1371.68292 |
| [62] | S.K. Ghosh and D.M. Mount. 1991. An output-sensitive algorithm for computing visibility graphs. SIAM J. Comput., 20, 5, 1991. Pages 888-910. · Zbl 0768.68202 |
| [63] | L.J. Guibas and J. Hershberger. 1989. Optimal shortest path queries in a simple polygon. J. Comput. System Sci., 39, 2, 1989. Pages 126-152. · Zbl 0681.68065 |
| [64] | L.J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R.E. Tarjan. 1987. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2, 1-4, 1987. Pages 209-233. · Zbl 0642.68081 |
| [65] | J. Hershberger. 1991. A new data structure for shortest path queries in a simple polygon. Inform. Process. Lett., 38, 5, 1991. Pages 231-235. · Zbl 0738.68021 |
| [66] | J. Hershberger and J. Snoeyink. 1994. Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications, 4, 1994. Pages 63-97. · Zbl 0815.68116 |
| [67] | J. Hershberger and S. Suri. 1999. An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput., 28, 1999. Pages 2215-2256. · Zbl 0939.68157 |
| [68] | J. Hershberger, S. Suri, and H. Y\i ld\i z. 2013. A near-optimal algorithm for shortest paths among curved obstacles in the plane. In Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG). Pages 359-368. · Zbl 1305.68239 |
| [69] | S. Hertel and K. Mehlhorn. 1985. Fast triangulation of the plane with respect to simple polygons. Information and Control, 64, 1985. Pages 52-76. · Zbl 0575.68049 |
| [70] | R. Inkulu, S. Kapoor, and S.N. Maheshwari. 2010. A near optimal algorithm for finding Euclidean shortest path in polygonal domain. In arXiv:1011.6481v1. |
| [71] | S. Kapoor and S.N. Maheshwari. 1988. Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In Proceedings of 4th Annual ACM Symposium on Computational Geometry (SoCG). Pages 172-182. |
| [72] | S. Kapoor and S.N. Maheshwari. 2000. Efficiently constructing the visibility graph of a simple polygon with obstacles. SIAM J. Comput., 30, 3, 2000. Pages 847-871. · Zbl 0966.68081 |
| [73] | S. Kapoor, S.N. Maheshwari, and J.S.B. Mitchell. 1997. An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discrete and Computational Geometry, 18, 1997. Pages 377-383. · Zbl 0892.68047 |
| [74] | D. Kirkpatrick. 1983. Optimal search in planar subdivisions. SIAM J. Comput., 12, 1983. Pages 28-35. · Zbl 0501.68034 |
| [75] | D. Kirkpatrick and J. Snoeyink. 1995. Tentative prune-and-search for computing fixed-points with applications to geometric computation. Fundamenta Informaticae, 22, 1995. Pages 353-370. · Zbl 0815.68119 |
| [76] | D.T. Lee and F.P. Preparata. 1984. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14, 1984. Pages 393-410. · Zbl 0545.90098 |
| [77] | J.S.B. Mitchell. 1989. An optimal algorithm for shortest rectilinear paths among obstacles. Abstracts of the \em 1st Canadian Conference on Computational Geometry. |
| [78] | J.S.B. Mitchell. 1991. A new algorithm for shortest paths among obstacles in the plane. Annals of Mathematics and Artificial Intelligence, 3, 1991. Pages 83-105. · Zbl 0875.68765 |
| [79] | J.S.B. Mitchell. 1992. L_1 shortest paths among polygonal obstacles in the plane. Algorithmica, 8, 1992. Pages 55-88. · Zbl 0753.68093 |
| [80] | J.S.B. Mitchell. 1996. Shortest paths among obstacles in the plane. International Journal of Computational Geometry and Applications, 6, 1996. Pages 309-332. · Zbl 0860.68109 |
| [81] | J.S.B. Mitchell and S. Suri. 1995. Separation and approximation of polyhedral objects. Computational Geometry: Theory and Applications, 5, 1995. Pages 95-114. · Zbl 0831.68113 |
| [82] | M. Overmars and J. van Leeuwen.. 1981. Maintenance of configurations in the plane. J. Comput. System Sci., 23, 1981. Pages 166-204. · Zbl 0474.68082 |
| [83] | H. Rohnert. 1986. Shortest paths in the plane with convex polygonal obstacles. Inform. Process. Lett., 23, 1986. Pages 71-76. · Zbl 0607.68052 |
| [84] | N. Sarnak and R.E. Tarjan. 1986. Planar point location using persistent search trees. Commun. ACM, 29, 1986. Pages 669-679. |
| [85] | M. Sharir and A. Schorr. 1986. On shortest paths in polyhedral spaces. SIAM J. Comput., 15, 1986. Pages 193-215. · Zbl 0612.68090 |
| [86] | J.A. Storer and J.H. Reif. 1994. Shortest paths in the plane with polygonal obstacles. J. ACM, 41, 1994. Pages 982-1012. · Zbl 0814.68129 |
| [87] | H. Wang. 2020. A divide-and-conquer algorithm for two-point L_1 shortest path queries in polygonal domains. Journal of Computational Geometry, 11, 2020. Pages 235-282. · Zbl 1477.68499 |
| [88] | H. Wang. 2021. Shortest paths among obstacles in the plane revisited. In Proceedings of the 32nd Annual Symposium on Discrete Algorithms (SODA). Pages 810-821. · Zbl 07788389 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
