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
1623319572 2096304547 2744874971 2130725973
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. 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 an O(n1.5)-space distance oracle for directed planar graphs that answers distance queries in O(log n) time. Our oracle both significantly simplifies and significantly improves the recent oracle of Cohen-Addad, Dahlgaard and Wulff-Nilsen [FOCS 2017], which uses O(n5 3)-space and answers queries in O(log n) time. We achieve this by designing an elegant and efficient point location data structure for Voronoi diagrams on planar graphs. We further show a smooth tradeoff between space and query-time. For any S ∈ [n, n2], we show an oracle of size S that answers queries in O(max 1, n1.5 S ) time. This new tradeoff is currently the best (up to polylogarithmic factors) for the entire range of S and improves by polynomial factors over all previously known tradeoffs for the range S ∈ [n, n5 3]. Thorup and Zwick, in the seminal paper [Journal of ACM, 52(1),2005, pp 1-24], showed that a weighted undirected graph onnvertices can be preprocessed in subcubic time to designa data structure which occupies only subquadratic space, and yet,for any pair of vertices, can answer distance query approximatelyin constant time. The data structure is termed as approximatedistance oracle. Subsequently, there has been improvement in theirpreprocessing time, and presently the best known algorithms [4,3]achieve expected O(n2) preprocessingtime for these oracles. For a class of graphs, these algorithmsindeed run in θ(n2) time. Inthis paper, we are able to break this quadratic barrier at theexpense of introducing a (small) constant additive error forunweighted graphs. In achieving this goal, we have been able topreserve the optimal size-stretch trade offs of the oracles. One ofour algorithms can be extended to weighted graphs, where theadditive error becomes 2·wmax(u,v) - herewmax(u,v) is the heaviestedge in the shortest path between vertices u,v.