Constant Query Time (1+∈)-Approximate Distance Oracle for Planar Graphs

摘要

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