Constant Query Time $(1+\epsilon )$-Approximate Distance Oracle for Planar Graphs

Abstract

We give a $(1+\epsilon )$-approximate distance oracle with $O(1)$ query time for an undirected planar graph $G$ with $n$ vertices and non-negative edge lengths. For $\epsilon >0$ and any two vertices $u$ and $v$ in $G$, our oracle gives a distance $\tilde{d}(u,v)$ with stretch $(1+\epsilon )$ in $O(1)$ time. The oracle has size $O(n\log n((\log n)/\epsilon +f(\epsilon )))$ and pre-processing time $O(n\log n(({\log }^{3}n)/{\epsilon }^2+f(\epsilon )))$, where $f(\epsilon )=2^{O(1/\epsilon )}$. This is the first $(1+\epsilon )$-approximate distance oracle with $O(1)$ query time independent of $\epsilon$ and the size and pre-processing time nearly linear in $n$, and improves the query time $O(1/\epsilon )$ of previous $(1+\epsilon )$-approximate distance oracle with size nearly linear in $n$.