We consider approximate distance oracles for edge-weighted n-vertex undirected planar graphs. Given fixed epsilon > 0, we present a (1+epsilon)-approximate distance oracle with O(n(loglog n)^2) space and O((loglog n)^3) query time. This improves the previous best product of query time and space of the oracles of Thorup (FOCS 2001, J. ACM 2004) and Klein (SODA 2002) from O(n log n) to O(n(loglog n)^5).
For a general undirected @math -vertex graph @math , Thorup and Zwick showed that for any parameter @math , there is a @math -approximate distance oracle for @math with @math space and @math query time which is believed to be essentially optimal due to a girth conjecture of Erd o s @cite_14 . Variations and slight improvements have since been presented; see, e.g., @cite_12 @cite_11 @cite_10 @cite_15 @cite_0 .
@cite_14 @cite_0 @cite_15 @cite_10 @cite_12 @cite_11
2158860088 2951814478 1601859867 2157760787
We give the first improvement to the space approximation trade-off of distance oracles since the seminal result of Thorup and Zwick. For unweighted undirected graphs, our distance oracle has size @math and, when queried about vertices at distance @math , returns a path of length at most 2d+1. For weighted undirected graphs with @math edges, our distance oracle has size @math and returns a factor 2 approximation. Based on a plausible conjecture about the hardness of set intersection queries, we show that a 2-approximate distance oracle requires space @math . For unweighted graphs, this implies a @math space lower bound to achieve approximation 2d+1. Given an undirected graph @math with @math edges, @math vertices, and non-negative edge weights, and given an integer @math , we show that for some universal constant @math , a @math -approximate distance oracle for @math of size @math can be constructed in @math time and can answer queries in @math time. We also give an oracle which is faster for smaller @math . Our results break the quadratic preprocessing time bound of Baswana and Kavitha for all @math and improve the @math time bound of Thorup and Zwick except for very sparse graphs and small @math . When @math and @math , our oracle is optimal w.r.t. both stretch, size, preprocessing time, and query time, assuming a widely believed girth conjecture by Erd o s. Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k ≥ 2, we show that a (2k − 1)-approximate distance oracle for G of size O(kn1+1 k) and with O(log k) query time can be constructed in O(min kmn1 k, √km + kn1+c √k ) time for some constant c. This improves the O(k) query time of Thorup and Zwick. Furthermore, for any 0 0 and k = O(log n log log n). Let G e (V, E) be an undirected graph on n vertices, and let Δ(u, v) denote the distance in G between two vertices u and v. Thorup and Zwick showed that for any positive integer t, the graph G can be preprocessed to build a data structure that can efficiently report t-approximate distance between any pair of vertices. That is, for any u, v ∈ V, the distance reported is at least Δ(u, v) and at most tΔ(u, v). The remarkable feature of this data structure is that, for t≥3, it occupies subquadratic space, that is, it does not store all-pairs distances explicitly, and still it can answer any t-approximate distance query in constant time. They named the data structure “approximate distance oracle” because of this feature. Furthermore, the trade-off between the stretch t and the size of the data structure is essentially optimal.In this article, we show that we can actually construct approximate distance oracles in expected O(n2) time if the graph is unweighted. One of the new ideas used in the improved algorithm also leads to the first expected linear-time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph. A (2, 1) spanner of an undirected unweighted graph G e (V, E) is a subgraph (V, E), E ⊆ E, such that for any two vertices u and v in the graph, their distance in the subgraph is at most 2Δ(u, v) p 1.