Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910337997996032 |
|---|---|
| author | de Berg, Sarita Miltzow, Tillmann Staals, Frank |
| author_facet | de Berg, Sarita Miltzow, Tillmann Staals, Frank |
| contents | 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 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 trade-off. Specifically, we devise data structures with $O(n^{9+\varepsilon}/\hspace{1pt} \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 with $O(\log n)$ query time 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})$. When both query points are on the boundary, the space complexity is decreased further to $O(n^{4+\varepsilon })$, thereby improving an earlier result of Bae and Okamoto. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_00666 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain de Berg, Sarita Miltzow, Tillmann Staals, Frank Computational Geometry Data Structures and Algorithms 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 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 trade-off. Specifically, we devise data structures with $O(n^{9+\varepsilon}/\hspace{1pt} \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 with $O(\log n)$ query time 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})$. When both query points are on the boundary, the space complexity is decreased further to $O(n^{4+\varepsilon })$, thereby improving an earlier result of Bae and Okamoto. |
| title | Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2303.00666 |