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).
Thorup @cite_16 also gave an oracle for planar which for polynomially bounded edge weights achieves @math space and close to @math query time. Exact oracles for planar digraphs with tradeoff between space and query time have been studied but require near-quadratic space for constant or near-constant query time @cite_4 @cite_13 .
@cite_13 @cite_16 @cite_4
2096304547 2950552904
For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an O(n 5 3)-space distance oracle which answers exact distance queries in O(log n) time for n-vertex planar edge-weighted digraphs. All previous distance oracles for planar graphs with truly subquadratic space (i.e., space O(n 2- ) for some constant 0) either required query time polynomial in n or could only answer approximate distance queries.Furthermore, we show how to trade-off time and space: for any S &#x2265; n 3 2, we show how to obtain an S-space distance 5 2 oracle that answers queries in time O(S n 3 2 log n). This is a polynomial improvement over the previous planar distance oracles with o(n 1 4) query time. It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space oracle that can answer reachability queries in constant time. The oracle can be distributed as an O(log n) space label for each vertex and then we can determine if one vertex can reach another considering their two labels only.The approach generalizes to give a near-linear space approximate distances oracle for a weighted planar digraph. With weights drawn from 0, …, N , it approximates distances within a factor (1 + e) in O(log log (nN) + 1 e) time. Our scheme can be extended to find and route along correspondingly short dipaths. We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following: * Given a desired space allocation @math , we show how to construct in @math time a data structure of size @math that answers distance queries in @math time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever @math . * We provide a linear-space exact distance oracle for planar graphs with query time @math for any constant eps>0. This is the first such data structure with provable sublinear query time. * For edge lengths at least one, we provide an exact distance oracle of space @math such that for any pair of nodes at distance D the query time is @math . Comparable query performance had been observed experimentally but has never been explained theoretically. Our data structures are based on the following new tool: given a non-self-crossing cycle C with @math nodes, we can preprocess G in @math time to produce a data structure of size @math that can answer the following queries in @math time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA'05), which reports distances to the boundary of a face, rather than a cycle. The best distance oracles for planar graphs until the current work are due to Cabello (SODA'06), Djidjev (WG'96), and Fakcharoenphol and Rao (FOCS'01). For @math and space @math , we essentially improve the query time from @math to @math . A (1+e)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing time. There are strong distance-oracle constructions known for planar graphs (Thorup, JACM'04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC'06). However, these require Ω(e-1n lg n) space for n-node graphs. In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only O(n) space. The big O hides only a fixed constant, independent of e and independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is O(nlg2 n). However, our constructions have slower query times. For planar graphs, the query time is O(e-2 lg2 n). For all our linear-space results, we can in fact ensure, for any δ > 0, that the space required is only 1 + δ times the space required just to represent the graph itself.