Faster Construction of a Planar Distance Oracle with Õ(1) Query Time

We show how to preprocess a weighted undirected $n$-vertex planar graph in $\tilde{O}(n^{4\mathrm{/}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\mathrm{/}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}(\mathrm{\mid }f\mathrm{\mid })$ time. This improves the $\tilde{O}(\sqrt{n\mathrm{\mid }f\mathrm{\mid }})$ construction time of [JACM’23].