{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T11:11:02Z","timestamp":1778238662524,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["VI.Vidi.213.150"],"award-info":[{"award-number":["VI.Vidi.213.150"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,7,31]]},"abstract":"\n We devise a data structure that can answer shortest path queries for two query points in a polygonal domain\n \n \\( P \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n on\n \n \\( n \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n vertices. For any\n \n \\(\\varepsilon > 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , the space complexity of the data structure is\n \n \\(O(n^{10+\\varepsilon})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and queries can be answered in\n \n \\(O(\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time. Alternatively, we can achieve a space complexity of\n \n \\(O(n^{9+\\varepsilon})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n by relaxing the query time to\n \n \\(O(\\log^{2}n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . This is the first improvement upon a conference paper by Chiang and Mitchell [\n 15<\/jats:xref>\n ] from 1999. They present a data structure with\n \n \\(O(n^{11})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n space complexity and\n \n \\(O(\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n query time. Our main result can be extended to include a space-time tradeoff. Specifically, we devise data structures with\n \n \\(O(n^{9+\\varepsilon}\/\\ell^{4+O(\\varepsilon)})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n space complexity and\n \n \\(O(\\ell\\log^{2}n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n query time, for any integer\n \n \\(1\\leq\\ell\\leq n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n Furthermore, we present improved data structures for the special case where we restrict one (or both) of the query points to lie on the boundary of\n \n \\( P \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . When one of the query points is restricted to lie on the boundary, and the other query point is unrestricted, the space complexity becomes\n \n \\(O(n^{6+\\varepsilon})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and the query time\n \n \\(O(\\log^{2}n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . When both query points are on the boundary, the space complexity is decreased further to\n \n \\(O(n^{4+\\varepsilon})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and the query time to\n \n \\(O(\\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , thereby improving an earlier result of Bae and Okamoto.\n <\/jats:p>","DOI":"10.1145\/3802821","type":"journal-article","created":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T14:23:54Z","timestamp":1774448634000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5555-966X","authenticated-orcid":false,"given":"Sarita","family":"de Berg","sequence":"first","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, Utrecht, The\u00a0Netherlands and IT University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4563-2864","authenticated-orcid":false,"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8522-1351","authenticated-orcid":false,"given":"Frank","family":"Staals","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,8]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"1","volume-title":"Proceedings of the 34th International Symposium on Computational Geometry (SoCG)","volume":"99","author":"Agarwal Pankaj K.","year":"2018","unstructured":"Pankaj K. Agarwal, Lars Arge, and Frank Staals. 2018. Improved dynamic geodesic nearest neighbor searching in a simple polygon. In Proceedings of the 34th International Symposium on Computational Geometry (SoCG). LIPIcs, Vol. 99, Article 4, 1\u201314."},{"key":"e_1_3_1_3_2","doi-asserted-by":"crossref","unstructured":"Pankaj K. Agarwal Boris Aronov Esther Ezra and Joshua Zahl. 2021. Efficient algorithm for generalized polynomial partitioning and its applications. SIAM Journal on Computing 50 2 (2021) 760\u2013787.","DOI":"10.1137\/19M1268550"},{"key":"e_1_3_1_4_2","doi-asserted-by":"crossref","unstructured":"Pankaj K. Agarwal Boris Aronov and Micha Sharir. 1997. Computing envelopes in four dimensions with applications. SIAM Journal on Computing 26 6 (1997) 1714\u20131732.","DOI":"10.1137\/S0097539794265724"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574015"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02716576"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9527-8"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.01.012"},{"key":"e_1_3_1_9_2","first-page":"1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG)","volume":"77","author":"Bonnet \u00c9douard","year":"2017","unstructured":"\u00c9douard Bonnet and Tillmann Miltzow. 2017. An approximation algorithm for the art gallery problem. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG). Boris Aronov and Matthew J. Katz (Eds.), LIPIcs, Vol. 77, Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 20, 1\u201315."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189314"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90261-Y"},{"key":"e_1_3_1_12_2","first-page":"292","volume-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chen Danny Z.","year":"1995","unstructured":"Danny Z. Chen. 1995. On the all-pairs Euclidean short path problem. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 292\u2013301."},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","unstructured":"Danny Z. Chen Ovidiu Daescu and Kevin S. Klenk. 2001. On geometric path query problems. International Journal of Computational Geometry & Applications 11 06 (2001) 617\u2013645.","DOI":"10.1142\/S0218195901000675"},{"key":"e_1_3_1_14_2","unstructured":"Danny Z. Chen Rajasekhar Inkulu and Haitao Wang. 2016. Two-point \\(L_{1}\\) shortest path queries in the plane. Journal of Computational Geometry 7 1 (2016) 473\u2013519."},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","unstructured":"Danny Z. Chen Kevin S. Klenk and Hung-Yi T. Tu. 2000. Shortest path queries among weighted obstacles in the rectilinear plane. SIAM Journal on Computing 29 4 (2000) 1223\u20131246.","DOI":"10.1137\/S0097539796307194"},{"key":"e_1_3_1_16_2","first-page":"215","volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chiang Yi-Jen","year":"1999","unstructured":"Yi-Jen Chiang and Joseph S. B. Mitchell. 1999. Two-point Euclidean shortest path queries in the plane. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 215\u2013224."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187879"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_1_20_2","doi-asserted-by":"crossref","unstructured":"Mark de Berg and Otfried Schwarzkopf. 1995. Cuttings and applications. International Journal of Computational Geometry & Applications 5 4 (1995) 343\u2013355.","DOI":"10.1142\/S0218195995000210"},{"key":"e_1_3_1_21_2","first-page":"1","volume-title":"Proceedings of the 40th International Symposium on Computational Geometry(SoCG \u201924)","volume":"293","author":"de Berg Sarita","year":"2024","unstructured":"Sarita de Berg, Tillmann Miltzow, and Frank Staals. 2024. Towards space efficient two-point shortest path queries in a polygonal domain. In Proceedings of the 40th International Symposium on Computational Geometry(SoCG \u201924). LIPIcs, Vol. 293, Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 17, 1\u201316."},{"key":"e_1_3_1_22_2","first-page":"1","volume-title":"Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC)","volume":"212","author":"de Berg Sarita","year":"2021","unstructured":"Sarita de Berg and Frank Staals. 2021. Dynamic data structures for \\( k \\) -nearest neighbor queries. In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC). LIPIcs, Vol. 212, Article 14, 1\u201314."},{"key":"e_1_3_1_23_2","first-page":"1","volume-title":"Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)","volume":"162","author":"Eades Patrick","year":"2020","unstructured":"Patrick Eades, Ivor van der Hoog, Maarten L\u00f6ffler, and Frank Staals. 2020. Trajectory visibility. In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT). LIPIcs, Vol. 162, Article 23, 1\u201322."},{"key":"e_1_3_1_24_2","doi-asserted-by":"crossref","unstructured":"Herbert Edelsbrunner Leonidas J. Guibas and Jorge Stolfi. 1986. Optimal point location in a monotone subdivision. SIAM Journal on Computing 15 2 (1986) 317\u2013340.","DOI":"10.1137\/0215023"},{"key":"e_1_3_1_25_2","doi-asserted-by":"crossref","unstructured":"Jeff Erickson. 2000. Space-time tradeoffs for emptiness queries. SIAM Journal on Computing 29 6 (2000) 1968\u20131996.","DOI":"10.1137\/S0097539798337212"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90041-X"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840360"},{"key":"e_1_3_1_28_2","first-page":"200","volume-title":"Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM)","volume":"5034","author":"Guo Hua","year":"2008","unstructured":"Hua Guo, Anil Maheshwari, and J\u00f6rg-R\u00fcdiger Sack. 2008. Shortest path queries in polygonal domains. In Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM). Lecture Notes in Computer Science, Vol. 5034, Springer, 200\u2013211."},{"key":"e_1_3_1_29_2","first-page":"229","volume-title":"Proceedings of the 39th European Workshop on Computational Geometry (EuroCG)","author":"Hagedoorn Mart","year":"2023","unstructured":"Mart Hagedoorn and Valentin Polishchuk. 2023. 2-point link distance queries in polygonal domains. In Proceedings of the 39th European Workshop on Computational Geometry (EuroCG), 229\u2013234."},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/2031416"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)90010-8"},{"key":"e_1_3_1_32_2","doi-asserted-by":"crossref","unstructured":"John Hershberger and Subhash Suri. 1999. An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on Computing 28 6 (1999) 2215\u20132256.","DOI":"10.1137\/S0097539795289604"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1017460.1017461"},{"key":"e_1_3_1_34_2","first-page":"1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"168","author":"Korman Matias","year":"2020","unstructured":"Matias Korman, Andr\u00e9 van Renssen, Marcel Roeloffzen, and Frank Staals. 2020. Kinetic geodesic Voronoi diagrams in a simple polygon. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP). LIPIcs, Vol. 168, Article 75, 1\u201317."},{"key":"e_1_3_1_35_2","first-page":"308","volume-title":"Proceedings of the 9th Annual Symposium on Computational Geometry (SoCG)","author":"Mitchell Joseph S. B.","year":"1993","unstructured":"Joseph S. B. Mitchell. 1993. Shortest paths among obstacles in the plane. In Proceedings of the 9th Annual Symposium on Computational Geometry (SoCG), 308\u2013317."},{"key":"e_1_3_1_36_2","first-page":"391","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Oh Eunjin","year":"2019","unstructured":"Eunjin Oh. 2019. Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 391\u2013409."},{"key":"e_1_3_1_37_2","doi-asserted-by":"crossref","unstructured":"Michel Pocchiola and Gert Vegter. 1996. The visibility complex. International Journal of Computational Geometry & Applications 06 03 (1996) 279\u2013308.","DOI":"10.1142\/S0218195996000204"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574384"},{"key":"e_1_3_1_39_2","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"Sharir Micha","year":"1995","unstructured":"Micha Sharir and Pankaj K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press."},{"key":"e_1_3_1_40_2","first-page":"383","volume-title":"Proceedings of the 15th Annual European Symposium (ESA)","volume":"4698","author":"Thorup Mikkel","year":"2007","unstructured":"Mikkel Thorup. 2007. Compact oracles for approximate distances around obstacles in the plane. In Proceedings of the 15th Annual European Symposium (ESA). Lecture Notes in Computer Science, Vol. 4698, Springer, 383\u2013394."},{"key":"e_1_3_1_41_2","unstructured":"Haitao Wang. 2018. On the geodesic centers of polygonal domains. Journal of Computational Geometry 9 1 (2018) 131\u2013190."},{"issue":"1","key":"e_1_3_1_42_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 Haitao","year":"2020","unstructured":"Haitao Wang. 2020. A divide-and-conquer algorithm for two-point \\(L_{1}\\) shortest path queries in polygonal domains. Journal of Computational Geometry 11, 1 (2020), 235\u2013282.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_1_43_2","first-page":"1","volume-title":"Proceedings of the 37th International Symposium on Computational Geometry (SoCG)","volume":"189","author":"Wang Haitao","year":"2021","unstructured":"Haitao Wang. 2021. An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons. In Proceedings of the 37th International Symposium on Computational Geometry (SoCG). LIPIcs, Vol. 189, Article 59, 1\u201315."},{"key":"e_1_3_1_44_2","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/1.9781611976465.51","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Wang Haitao","year":"2021","unstructured":"Haitao Wang. 2021. Shortest paths among obstacles in the plane revisited. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 810\u2013821."},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3580475"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802821","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T10:52:46Z","timestamp":1778237566000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802821"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,8]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,7,31]]}},"alternative-id":["10.1145\/3802821"],"URL":"https:\/\/doi.org\/10.1145\/3802821","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,8]]},"assertion":[{"value":"2024-11-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-05-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}