More Compact Oracles for Approximate Distances in Undirected Planar Graphs

Ken-ichi Kawarabayashi, Christian Sommer, and Mikkel Thorup
SODA 2013 - 24th ACM-SIAM Symposium on Discrete Algorithms (pp. 550-563)

Distance oracles are data structures that provide fast (possibly approximate) answers to shortest-path and distance queries in graphs. The tradeoff between the space requirements and the query time of distance oracles is of particular interest and the main focus of this paper. Unless stated otherwise, we assume all graphs to be planar and undirected.

In FOCS 2001 (J. ACM 2004), Thorup introduced approximate distance oracles for planar graphs, proving that, for any \(\epsilon \gt 0\) and for any undirected planar graph on \(n\) nodes, there exists a \((1 + \epsilon)\)-approximate distance oracle using space \(O(n \epsilon^{-1}\log n)\) such that approximate distance queries can be answered in time \(O(1/\epsilon)\). The time-space product is \(O(n \epsilon^{-2}\log n)\).

We note that we may easily have \(1/\epsilon \gt \log n\), e.g., if a 1% error is desired. In this paper, we aim at reducing the polynomial dependency on \(1/\epsilon\) and \(\log n\), getting the first improvement in the time-space product. To simplify the statement of our bounds, we define \(\bar{O}(\cdot)\) to hide \(\log\log n\) and \(\log (1/\epsilon)\) factors.

• We provide the first oracle with a time-space product that is subquadratic in \(1/\epsilon\). We obtain an oracle with space \(\bar{O}(n\log n)\) and query time \(\bar{O}(1/\epsilon)\).
• For unweighted graphs we show how the logarithmic dependency on \(n\), which is quite common in separator-based approaches, can be removed completely. We obtain an oracle with space \(\bar{O}(n)\) and query time \(\bar{O}(1/\epsilon)\). This bound also holds for graphs with polylogarithmic average edge length, which may be a quite reasonable assumption, e.g., for road networks.

@inproceedings{KST13,
 author    = {{Ken-ichi} Kawarabayashi 
              and Christian Sommer 
              and Mikkel Thorup},
 title     = {More Compact Oracles for Approximate Distances 
              in Undirected Planar Graphs},
 year      = {2013},
 booktitle = {24th ACM-SIAM Symposium on Discrete Algorithms (SODA)},
 pages     = {550--563},
 url       = {http://dx.doi.org/10.1137/1.9781611973105.40},
 doi       = {10.1137/1.9781611973105.40},
}

Official version
Local version (344.6 KB)
arXiv

Home → Publications → More Compact Oracles for Approximate Distances in Undirected Planar Graphs