More compact oracles for approximate distances in undirected planar graphs

TY - GEN

T1 - More compact oracles for approximate distances in undirected planar graphs

AU - Kawarabayashi, Ken-ichi

AU - Sommer, Christian

AU - Thorup, Mikkel

N1 - Conference code: 24

PY - 2013

Y1 - 2013

N2 - 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 (concurrent with Klein, SODA 2002). Thorup proved that, for any ε > 0 and for any undirected planar graph G = (V, E) on n = |V| nodes, there exists a (1 + ε)-approximate distance oracle using space O(nε-1 log n) such that approximate distance queries can be answered in time O(ε-1). In this paper, we aim at reducing the polynomial dependency on ε-1 and log n, getting the first improvement in the query time-space tradeoff. To simplify the statement of our bounds, we define Ō(·) to hide log log n and log(1/ε) factors. • We provide the first oracle with a time-space product that is subquadratic in ε-1. We obtain an oracle with space Ō(n log n) and query time Ō(ε-1). • For unweighted graphs we show how the logarithmic dependency on n can be removed. We obtain an oracle with space Ō(n) and query time Ō(ε-1). This bound also holds for graphs with polylogarithmic average edge length, which may be a quite reasonable assumption, e.g., for road networks.

AB - 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 (concurrent with Klein, SODA 2002). Thorup proved that, for any ε > 0 and for any undirected planar graph G = (V, E) on n = |V| nodes, there exists a (1 + ε)-approximate distance oracle using space O(nε-1 log n) such that approximate distance queries can be answered in time O(ε-1). In this paper, we aim at reducing the polynomial dependency on ε-1 and log n, getting the first improvement in the query time-space tradeoff. To simplify the statement of our bounds, we define Ō(·) to hide log log n and log(1/ε) factors. • We provide the first oracle with a time-space product that is subquadratic in ε-1. We obtain an oracle with space Ō(n log n) and query time Ō(ε-1). • For unweighted graphs we show how the logarithmic dependency on n can be removed. We obtain an oracle with space Ō(n) and query time Ō(ε-1). This bound also holds for graphs with polylogarithmic average edge length, which may be a quite reasonable assumption, e.g., for road networks.

U2 - 10.1137/1.9781611973105.40

DO - 10.1137/1.9781611973105.40

M3 - Article in proceedings

SN - 978-1-61197-251-1

SP - 550

EP - 563

BT - Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Khanna, Sanjeev

PB - Association for Computing Machinery

T2 - Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 6 January 2013 through 8 January 2013

ER -