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

Abstract

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].