{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T15:15:23Z","timestamp":1775229323497,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,3,21]],"date-time":"2023-03-21T00:00:00Z","timestamp":1679356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-2005323, CCF-2300356"],"award-info":[{"award-number":["CCF-2005323, CCF-2300356"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri (in<jats:italic>SIAM Journal on Computing<\/jats:italic>, 1999) gave an algorithm of<jats:italic>O(n<\/jats:italic>log<jats:italic>n<\/jats:italic>) time and<jats:italic>O(n<\/jats:italic>log<jats:italic>n<\/jats:italic>) space, where<jats:italic>n<\/jats:italic>is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri\u2019s algorithm, Wang (in SODA\u201921) reduced the space to<jats:italic>O(n)<\/jats:italic>while the runtime of the algorithm is still<jats:italic>O(n<\/jats:italic>log<jats:italic>n<\/jats:italic>). In this article, we present a new algorithm of<jats:italic>O(n+h<\/jats:italic>log<jats:italic>h<\/jats:italic>) time and<jats:italic>O(n)<\/jats:italic>space, provided that a triangulation of the free space is given, where<jats:italic>h<\/jats:italic>is the number of obstacles. The algorithm is better than the previous work when<jats:italic>h<\/jats:italic>is relatively small. Our algorithm builds a shortest path map for a source point<jats:italic>s<\/jats:italic>so that given any query point<jats:italic>t<\/jats:italic>, the shortest path length from<jats:italic>s<\/jats:italic>to<jats:italic>t<\/jats:italic>can be computed in<jats:italic>O<\/jats:italic>(log<jats:italic>n<\/jats:italic>) time and a shortest<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>path can be produced in additional time linear in the number of edges of the path.<\/jats:p>","DOI":"10.1145\/3580475","type":"journal-article","created":{"date-parts":[[2023,3,21]],"date-time":"2023-03-21T12:11:50Z","timestamp":1679400710000},"page":"1-62","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["A New Algorithm\u00a0for Euclidean Shortest Paths in the Plane"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8134-7409","authenticated-orcid":false,"given":"Haitao","family":"Wang","sequence":"first","affiliation":[{"name":"University of Utah, Salt Lake City, UT"}]}],"member":"320","published-online":{"date-parts":[[2023,3,21]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.tcs.2019.04.023","article-title":"L1 shortest path queries in simple polygons","volume":"790","author":"Bae S. W.","year":"2019","unstructured":"S. W. Bae and H. Wang. 2019. L1 shortest path queries in simple polygons. Theoretical Computer Science 790 (2019), 105\u2013116.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1142\/S0218195994000252","article-title":"Triangulating disjoint Jordan chains","volume":"4","author":"Bar-Yehuda R.","year":"1994","unstructured":"R. Bar-Yehuda and B. Chazelle. 1994. Triangulating disjoint Jordan chains. International Journal of Computational Geometry and Applications 4, 4 (1994), 475\u2013481.","journal-title":"International Journal of Computational Geometry and Applications"},{"issue":"3","key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"1158","DOI":"10.1137\/110840030","article-title":"Computing shortest paths amid convex pseudodisks","volume":"42","author":"Chen D. Z.","year":"2013","unstructured":"D. Z. Chen, J. Hershberger, and H. Wang. 2013. Computing shortest paths amid convex pseudodisks. SIAM Journal on Computing 42, 3 (2013), 1158\u20131184.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_5_2","first-page":"473","article-title":"Two-point \\(L_1\\) shortest path queries in the plane","volume":"1","author":"Chen D. Z.","year":"2016","unstructured":"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), 473\u2013519.","journal-title":"Journal of Computational Geometry"},{"issue":"4","key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"1223","DOI":"10.1137\/S0097539796307194","article-title":"Shortest path queries among weighted obstacles in the rectilinear plane","volume":"29","author":"Chen D. Z.","year":"2000","unstructured":"D. Z. Chen, K. S. Klenk, and H.-Y. T. Tu. 2000. Shortest path queries among weighted obstacles in the rectilinear plane. SIAM Journal on Computing 29, 4 (2000), 1223\u20131246.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_7_2","article-title":"Computing shortest paths among curved obstacles in the plane","volume":"11","author":"Chen D. Z.","year":"2015","unstructured":"D. Z. Chen and H. Wang. 2015. Computing shortest paths among curved obstacles in the plane. ACM Transactions on Algorithms 11 (2015), Article 26.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_2_8_2","first-page":"316","article-title":"A new algorithm for computing visibility graphs of polygonal obstacles in the plane","volume":"6","author":"Chen D. Z.","year":"2015","unstructured":"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), 316\u2013345.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/s00453-015-0058-y","article-title":"Computing the visibility polygon of an island in a polygonal domain","volume":"77","author":"Chen D. Z.","year":"2017","unstructured":"D. Z. Chen and H. Wang. 2017. Computing the visibility polygon of an island in a polygonal domain. Algorithmica 77 (2017), 40\u201364.","journal-title":"Algorithmica"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"2430","DOI":"10.1007\/s00453-018-00540-x","article-title":"Computing \\(L_1\\) shortest paths among polygonal obstacles in the plane.","volume":"81","author":"Chen D. Z.","year":"2019","unstructured":"D. Z. Chen and H. Wang. 2019. Computing \\(L_1\\) shortest paths among polygonal obstacles in the plane. Algorithmica 81 (2019), 2430\u20132483.","journal-title":"Algorithmica"},{"key":"e_1_3_2_11_2","first-page":"215","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999)","author":"Chiang Y.-J.","year":"1999","unstructured":"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\u201999). 215\u2013224."},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1142\/S0218195992000081","article-title":"Randomized parallel algorithms for trapezoidal diagrams","volume":"2","author":"Clarkson K. L.","year":"1992","unstructured":"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), 117\u2013133.","journal-title":"International Journal of Computational Geometry and Application"},{"key":"e_1_3_2_13_2","first-page":"251","volume-title":"Proceedings of the 3rd Annual Symposium on Computational Geometry (SoCG\u201987)","author":"Clarkson K.","year":"1987","unstructured":"K. Clarkson, S. Kapoor, and P. Vaidya. 1987. Rectilinear shortest paths through polygonal obstacles in \\(O(n \\log ^2 n)\\) time. In Proceedings of the 3rd Annual Symposium on Computational Geometry (SoCG\u201987). 251\u2013257."},{"key":"e_1_3_2_14_2","article-title":"Rectilinear shortest paths through polygonal obstacles in \\(O(n \\log ^{2\/3} n)\\) time","author":"Clarkson K.","year":"1988","unstructured":"K. Clarkson, S. Kapoor, and P. Vaidya. 1988. Rectilinear shortest paths through polygonal obstacles in \\(O(n \\log ^{2\/3} n)\\) time. Manuscript.","journal-title":"Manuscript"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02187714","article-title":"Rectilinear shortest paths in the presence of rectangular barriers","volume":"4","author":"Rezende P. J. de","year":"1989","unstructured":"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), 41\u201353.","journal-title":"Discrete and Computational Geometry"},{"key":"e_1_3_2_16_2","unstructured":"E. D. Demaine J. S. B. Mitchell and J. O\u2019Rourke. 2020. The Open Problems Project. Retrieved January 23 2023 from https:\/\/topp.openproblem.net\/."},{"issue":"2","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","article-title":"Optimal point location in a monotone subdivision","volume":"15","author":"Edelsbrunner H.","year":"1986","unstructured":"H. Edelsbrunner, L. Guibas, and J. Stolfi. 1986. Optimal point location in a monotone subdivision. SIAM Journal on Computing 15, 2 (1986), 317\u2013340.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_18_2","first-page":"1616","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Eriksson-Bique S. D.","year":"2015","unstructured":"S. D. Eriksson-Bique, J. Hershberger, V. Polishchuk, B. Speckmann, S. Suri, T. Talvitie, K. Verbeek, and H. Y\u0131ld\u0131z. 2015. Geometric k shortest paths. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). 1616\u20131625."},{"issue":"5","key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1137\/0220055","article-title":"An output-sensitive algorithm for computing visibility graphs","volume":"20","author":"Ghosh S. K.","year":"1991","unstructured":"S. K. Ghosh and D. M. Mount. 1991. An output-sensitive algorithm for computing visibility graphs. SIAM Journal on Computing 20, 5 (1991), 888\u2013910.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0022-0000(89)90041-X","article-title":"Optimal shortest path queries in a simple polygon","volume":"39","author":"Guibas L. J.","year":"1989","unstructured":"L. J. Guibas and J. Hershberger. 1989. Optimal shortest path queries in a simple polygon. Journal of Computer and System Sciences 39, 2 (1989), 126\u2013152.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","article-title":"Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons","volume":"2","author":"Guibas L. J.","year":"1987","unstructured":"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), 209\u2013233.","journal-title":"Algorithmica"},{"issue":"1","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0218195991000025","article-title":"Compact interval trees: A data structure for convex hulls","volume":"1","author":"Guibas L.","year":"1991","unstructured":"L. Guibas, J. Hershberger, and J. Snoeyink. 1991. Compact interval trees: A data structure for convex hulls. International Journal of Computational Geometry and Applications 1, 1 (1991), 1\u201322.","journal-title":"International Journal of Computational Geometry and Applications"},{"issue":"5","key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0020-0190(91)90064-O","article-title":"A new data structure for shortest path queries in a simple polygon","volume":"38","author":"Hershberger J.","year":"1991","unstructured":"J. Hershberger. 1991. A new data structure for shortest path queries in a simple polygon. Information Processing Letters 38, 5 (1991), 231\u2013235.","journal-title":"Information Processing Letters"},{"key":"e_1_3_2_24_2","first-page":"Article 96, 2 p","volume-title":"Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG\u201914)","author":"Hershberger J.","year":"2014","unstructured":"J. Hershberger, V. Polishchuk, B. Speckmann, and T. Talvitie. 2014. Geometric kth shortest paths. In Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG\u201914). Article 96, 2 pages. http:\/\/www.computational-geometry.org\/SoCG-videos\/socg14video\/ksp\/applet\/index.html."},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0925-7721(94)90010-8","article-title":"Computing minimum length paths of a given homotopy class","volume":"4","author":"Hershberger J.","year":"1994","unstructured":"J. Hershberger and J. Snoeyink. 1994. Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications 4 (1994), 63\u201397.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"2215","DOI":"10.1137\/S0097539795289604","article-title":"An optimal algorithm for Euclidean shortest paths in the plane","volume":"28","author":"Hershberger J.","year":"1999","unstructured":"J. Hershberger and S. Suri. 1999. An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on Computing 28 (1999), 2215\u20132256.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1145\/2462356.2462374","volume-title":"Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG\u201913)","author":"Hershberger J.","year":"2013","unstructured":"J. Hershberger, S. Suri, and H. Y\u0131ld\u0131z. 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\u201913). 359\u2013368."},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/S0019-9958(85)80044-9","article-title":"Fast triangulation of the plane with respect to simple polygons","volume":"64","author":"Hertel S.","year":"1985","unstructured":"S. Hertel and K. Mehlhorn. 1985. Fast triangulation of the plane with respect to simple polygons. Information and Control 64 (1985), 52\u201376.","journal-title":"Information and Control"},{"key":"e_1_3_2_29_2","volume-title":"arXiv:1011.6481v1","author":"Inkulu R.","year":"2010","unstructured":"R. Inkulu, S. Kapoor, and S. N. Maheshwari. 2010. A near optimal algorithm for finding Euclidean shortest path in polygonal domain. arXiv:1011.6481v1 (2010)."},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1145\/73393.73411","volume-title":"Proceedings of the 4th Annual ACM Symposium on Computational Geometry (SoCG\u201988)","author":"Kapoor S.","year":"1988","unstructured":"S. Kapoor and S. N. Maheshwari. 1988. Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles. In Proceedings of the 4th Annual ACM Symposium on Computational Geometry (SoCG\u201988). 172\u2013182."},{"issue":"3","key":"e_1_3_2_31_2","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1137\/S0097539795253591","article-title":"Efficiently constructing the visibility graph of a simple polygon with obstacles","volume":"30","author":"Kapoor S.","year":"2000","unstructured":"S. Kapoor and S. N. Maheshwari. 2000. Efficiently constructing the visibility graph of a simple polygon with obstacles. SIAM Journal on Computing 30, 3 (2000), 847\u2013871.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/PL00009323","article-title":"An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane","volume":"18","author":"Kapoor S.","year":"1997","unstructured":"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), 377\u2013383.","journal-title":"Discrete and Computational Geometry"},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","article-title":"Optimal search in planar subdivisions","volume":"12","author":"Kirkpatrick D.","year":"1983","unstructured":"D. Kirkpatrick. 1983. Optimal search in planar subdivisions. SIAM Journal on Computing 12 (1983), 28\u201335.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"353","DOI":"10.3233\/FI-1995-2243","article-title":"Tentative prune-and-search for computing fixed-points with applications to geometric computation","volume":"22","author":"Kirkpatrick D.","year":"1995","unstructured":"D. Kirkpatrick and J. Snoeyink. 1995. Tentative prune-and-search for computing fixed-points with applications to geometric computation. Fundamenta Informaticae 22 (1995), 353\u2013370.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","article-title":"Euclidean shortest paths in the presence of rectilinear barriers","volume":"14","author":"Lee D. T.","year":"1984","unstructured":"D. T. Lee and F. P. Preparata. 1984. Euclidean shortest paths in the presence of rectilinear barriers. Networks 14 (1984), 393\u2013410.","journal-title":"Networks"},{"key":"e_1_3_2_36_2","article-title":"An optimal algorithm for shortest rectilinear paths among obstacles","author":"Mitchell J. S. B.","year":"1989","unstructured":"J. S. B. Mitchell. 1989. An optimal algorithm for shortest rectilinear paths among obstacles. In Abstracts of the 1st Canadian Conference on Computational Geometry.","journal-title":"Abstracts of the 1st Canadian Conference on Computational Geometry"},{"key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01530888","article-title":"A new algorithm for shortest paths among obstacles in the plane","volume":"3","author":"Mitchell J. S. B.","year":"1991","unstructured":"J. S. B. Mitchell. 1991. A new algorithm for shortest paths among obstacles in the plane. Annals of Mathematics and Artificial Intelligence 3 (1991), 83\u2013105.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01758836","article-title":"\\(L_1\\) shortest paths among polygonal obstacles in the plane","volume":"8","author":"Mitchell J. S. B.","year":"1992","unstructured":"J. S. B. Mitchell. 1992. \\(L_1\\) shortest paths among polygonal obstacles in the plane. Algorithmica 8 (1992), 55\u201388.","journal-title":"Algorithmica"},{"key":"e_1_3_2_39_2","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1142\/S0218195996000216","article-title":"Shortest paths among obstacles in the plane","volume":"6","author":"Mitchell J. S. B.","year":"1996","unstructured":"J. S. B. Mitchell. 1996. Shortest paths among obstacles in the plane. International Journal of Computational Geometry and Applications 6 (1996), 309\u2013332.","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0925-7721(95)00006-U","article-title":"Separation and approximation of polyhedral objects","volume":"5","author":"Mitchell J. S. B.","year":"1995","unstructured":"J. S. B. Mitchell and S. Suri. 1995. Separation and approximation of polyhedral objects. Computational Geometry: Theory and Applications 5 (1995), 95\u2013114.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1137\/1.9781611975482.25","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Oh E.","year":"2019","unstructured":"E. Oh. 2019. Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919). 391\u2013409."},{"key":"e_1_3_2_42_2","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","article-title":"Maintenance of configurations in the plane","volume":"23","author":"Overmars M.","year":"1981","unstructured":"M. Overmars and J. van Leeuwen.1981. Maintenance of configurations in the plane. Journal of Computer and System Sciences 23 (1981), 166\u2013204.","journal-title":"Journal of Computer and System Sciences"},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0020-0190(86)90045-1","article-title":"Shortest paths in the plane with convex polygonal obstacles","volume":"23","author":"Rohnert H.","year":"1986","unstructured":"H. Rohnert. 1986. Shortest paths in the plane with convex polygonal obstacles. Information Processing Letters 23 (1986), 71\u201376.","journal-title":"Information Processing Letters"},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","article-title":"Planar point location using persistent search trees","volume":"29","author":"Sarnak N.","year":"1986","unstructured":"N. Sarnak and R. E. Tarjan. 1986. Planar point location using persistent search trees. Communications of the ACM 29 (1986), 669\u2013679.","journal-title":"Communications of the ACM"},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0215014","article-title":"On shortest paths in polyhedral spaces","volume":"15","author":"Sharir M.","year":"1986","unstructured":"M. Sharir and A. Schorr. 1986. On shortest paths in polyhedral spaces. SIAM Journal on Computing 15 (1986), 193\u2013215.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_46_2","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1145\/185675.185795","article-title":"Shortest paths in the plane with polygonal obstacles","volume":"41","author":"Storer J. A.","year":"1994","unstructured":"J. A. Storer and J. H. Reif. 1994. Shortest paths in the plane with polygonal obstacles. Journal of the ACM 41 (1994), 982\u20131012.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_47_2","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/s00454-019-00108-8","article-title":"Quickest visibility queries in polygonal domains","volume":"62","author":"Wang H.","year":"2019","unstructured":"H. Wang. 2019. Quickest visibility queries in polygonal domains. Discrete and Computational Geometry 62 (2019), 374\u2013432.","journal-title":"Discrete and Computational Geometry"},{"key":"e_1_3_2_48_2","first-page":"235","article-title":"A divide-and-conquer algorithm for two-point \\(L_1\\) shortest path queries in polygonal domains","volume":"11","author":"Wang H.","year":"2020","unstructured":"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), 235\u2013282.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_2_49_2","first-page":"810","volume-title":"Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921)","author":"Wang H.","year":"2021","unstructured":"H. Wang. 2021. Shortest paths among obstacles in the plane revisited. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921). 810\u2013821."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580475","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:42Z","timestamp":1750178262000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580475"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,21]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3580475"],"URL":"https:\/\/doi.org\/10.1145\/3580475","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,21]]},"assertion":[{"value":"2021-06-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-10","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}