Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916660678492160 |
|---|---|
| author | Boneh, Itai Golan, Shay Mozes, Shay Prigan, Daniel Weimann, Oren |
| author_facet | Boneh, Itai Golan, Shay Mozes, Shay Prigan, Daniel Weimann, Oren |
| contents | We show how to preprocess a weighted undirected $n$-vertex planar graph in $\tilde O(n^{4/3})$ time, such that the distance between any pair of vertices can then be reported in $\tilde O(1)$ time. This improves the previous $\tilde O(n^{3/2})$ preprocessing time [JACM'23].
Our main technical contribution is a near optimal construction of \emph{additively weighted Voronoi diagrams} in undirected planar graphs. Namely, given a planar graph $G$ and a face $f$, we show that one can preprocess $G$ in $\tilde O(n)$ time such that given any weight assignment to the vertices of $f$ one can construct the additively weighted Voronoi diagram of $f$ in near optimal $\tilde O(|f|)$ time. This improves the $\tilde O(\sqrt{n |f|})$ construction time of [JACM'23]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_18425 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Construction of a Planar Distance Oracle with Õ(1) Query Time Boneh, Itai Golan, Shay Mozes, Shay Prigan, Daniel Weimann, Oren Data Structures and Algorithms We show how to preprocess a weighted undirected $n$-vertex planar graph in $\tilde O(n^{4/3})$ time, such that the distance between any pair of vertices can then be reported in $\tilde O(1)$ time. This improves the previous $\tilde O(n^{3/2})$ preprocessing time [JACM'23]. Our main technical contribution is a near optimal construction of \emph{additively weighted Voronoi diagrams} in undirected planar graphs. Namely, given a planar graph $G$ and a face $f$, we show that one can preprocess $G$ in $\tilde O(n)$ time such that given any weight assignment to the vertices of $f$ one can construct the additively weighted Voronoi diagram of $f$ in near optimal $\tilde O(|f|)$ time. This improves the $\tilde O(\sqrt{n |f|})$ construction time of [JACM'23]. |
| title | Faster Construction of a Planar Distance Oracle with Õ(1) Query Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.18425 |