Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
ACM Transactions on Algorithms · 31.07.2026 · 22 (3) · 1-27
DOI: 10.1145/3802821 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 08.05.2026. Verfasst von Sarita de Berg und 2 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben. Gefördert von: Netherlands Organisation for Scientific Research.
Abstract (Originalsprache)
We devise a data structure that can answer shortest path queries for two query points in a polygonal domain \( P \) on \( n \) vertices. For any \(\varepsilon > 0\) , the space complexity of the data structure is \(O(n^{10+\varepsilon})\) and queries can be answered in \(O(\log n)\) time. Alternatively, we can achieve a space complexity of \(O(n^{9+\varepsilon})\) by relaxing the query time to \(O(\log^{2}n)\) . This is the first improvement upon a conference paper by Chiang and Mitchell [ 15 ] from 1999. They present a data structure with \(O(n^{11})\) space complexity and \(O(\log n)\) query time. Our main result can be extended to include a space-time tradeoff. Specifically, we devise data structures with \(O(n^{9+\varepsilon}/\ell^{4+O(\varepsilon)})\) space complexity and \(O(\ell\log^{2}n)\) query time, for any integer \(1\leq\ell\leq 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 \( P \) . When one of the query points is restricted to lie on the boundary, and the other query point is unrestricted, the space complexity becomes \(O(n^{6+\varepsilon})\) and the query time \(O(\log^{2}n)\) . When both query points are on the boundary, the space complexity is decreased further to \(O(n^{4+\varepsilon})\) and the query time to \(O(\log n)\) , thereby improving an earlier result of Bae and Okamoto.
Förderung
- Netherlands Organisation for Scientific Research
Zitieren
APA
Berg, S. D., Miltzow, T., & Staals, F. (2026). Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain. ACM Transactions on Algorithms, 22(3), 1-27. https://doi.org/10.1145/3802821
Vancouver
Berg SD, Miltzow T, Staals F. Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain. ACM Transactions on Algorithms. 2026;22(3):1-27. doi:10.1145/3802821
BibTeX
@article{Berg2026,
author = {Berg, Sarita de and Miltzow, Tillmann and Staals, Frank},
title = {Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain},
journal = {ACM Transactions on Algorithms},
year = {2026},
volume = {22},
number = {3},
pages = {1--27},
doi = {10.1145/3802821}
}
EUVIMED