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. 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. We give the first improvement to the space approximation trade-off of distance oracles since the seminal result of Thorup and Zwick [STOC'01]. For unweighted graphs, our distance oracle has size @math and, when queried about vertices at distance @math , returns a path of length @math . For weighted 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 @math . 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. 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]. An approximate distance oracle is a succinct data structure that provides fast answers to distance queries between any two nodes. In this paper we consider approximate distance oracles for general undirected graphs with non-negative edge weights with constant query time. We present a distance oracle of size O(k n^ 1+1 k ), with 2k-1 stretch and O(1) query time. This improves the O(log k ) query time of Wulff-Nilsen's distance oracle [SODA '13], which in turn improved the O(k) query time of Thorup and Zwick's distance oracle [J. ACM '05]. An approximate distance oracle is a succinct data structure that provides fast answers to distance queries between any two nodes of a given graph. In this paper we consider approximate distance oracles for general undirected graphs with non-negative edge weights with constant query time. We present a distance oracle of size O(kn1+1 k), with 2k --- 1 stretch and O(1) query time. This improves the O(log k) query time of Wulff-Nilsen's distance oracle [SODA '13], which in turn improved the O(k) query time of Thorup and Zwick's distance oracle [J. ACM '05]. This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman in BFM86 ). We then proceed to construct optimal Ramsey partitions, and use them to show that for every @math , every @math -point metric space has a subset of size @math which embeds into Hilbert space with distortion @math . This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor BLMN05 , in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick in TZ05 . Namely, we show that for every @math point metric space @math , and @math , there exists an @math -approximate distance oracle whose storage requirement is @math , and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking. 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. This paper addresses the non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce and construct optimal Ramsey partitions, and use them to show that for every (0, 1), any n-point metric space has a subset of size n^ 1 - which embeds into Hilbert space with distortion O(1 ). This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor [5], in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick in [26]. Namely, we show that for any n point metric space X, and k 1, there exists an O(k)-approximate distance oracle whose storage requirement is O(n^ 1 + 1 k ), and whose query time is a universal constant. We also discuss applications to various other geometric data structures, and the relation to well separated pair decompositions. We consider distance queries in vertex-labeled planar graphs. For any fixed @math we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex @math and a label @math return a @math -approximation of the distance from @math to its closest vertex with label @math . For a directed planar graph with @math vertices, such that the ratio of the largest to smallest arc length is bounded by @math , the preprocessing time is @math , the data structure size is @math , and the query time is @math . We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect. 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). We investigate the problem of approximate Nearest-Neighbor Search (NNS) in graphical metrics: The task is to preprocess an edge-weighted graph G=(V,E) on m vertices and a small "dataset" D V of size n << m, so that given a query point q V, one can quickly approximate dist(q,D) (the distance from q to its closest vertex in D) and find a vertex a D within this approximated distance. We assume the query algorithm has access to a distance oracle, that quickly evaluates the exact distance between any pair of vertices. For planar graphs G with maximum degree Delta, we show how to efficiently construct a compact data structure -- of size O(n(Delta+1 epsilon)) -- that answers (1+epsilon)-NNS queries in time O(Delta+1 epsilon). Thus, as far as NNS applications are concerned, metrics derived from bounded-degree planar graphs behave as low-dimensional metrics, even though planar metrics do not necessarily have a low doubling dimension, nor can they be embedded with low distortion into l_2. We complement our algorithmic result by lower bounds showing that the access to an exact distance oracle (rather than an approximate one) and the dependency on Delta (in query time) are both essential. We consider vertex-labeled graphs, where each vertex v is attached with a label from a set of labels. The vertex-to-label distance query desires the length of the shortest path from the given vertex to the set of vertices with the given label. We show how to construct an oracle for a vertex-labeled planar graph, such that (O( 1 n n) ) storing space is needed, and any vertex-to-label query can be answered in (O( 1 n ) ) time with stretch 1 + e. Here, Δ is the hop-diameter of the given graph. For the case that Δ = O(logn), we construct a distance oracle that achieves (O( 1 n) ) query time, without changing space usage. We consider the problem of encoding graphs with n vertices and m edges compactly supporting adjacency, neighborhood and degree queries in constant time in the @Q(logn)-bit word RAM model. The adjacency query asks whether there is an edge between two vertices, the neighborhood query reports the neighbors of a given vertex in constant time per neighbor, and the degree query reports the number of incident edges to a given vertex. We study the problem in the context of succinctness, where the goal is to achieve the optimal space requirement as a function of n and m, to within lower order terms. We prove a lower bound in the cell probe model indicating it is impossible to achieve the information-theory lower bound up to lower order terms unless the graph is either too sparse (namely, m=o(n^@d) for any constant @d>0) or too dense (namely m=@w(n^2^-^@d) for any constant @d>0). Furthermore, we present a succinct encoding of graphs supporting aforementioned queries in constant time. The space requirement of the encoding is within a multiplicative 1+@e factor of the information-theory lower bound for any arbitrarily small constant @e>0. This is the best achievable space bound according to our lower bound where it applies. The space requirement of the representation achieves the information-theory lower bound tightly within lower order terms where the graph is very sparse (m=o(n^@d) for any constant @d>0), or very dense (m>n^2 lg^1^-^@dn for an arbitrarily small constant @d>0). We describe algorithms for finding shortest paths and distances in outerplanar and planar digraphs that exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. In the case of outerplanar digraphs, our data structures can be updated after any such change in only logarithmic time. A distance query is also answered in logarithmic time. In the case of planar digraphs, we give an interesting tradeoff between preprocessing, query, and update times depending on the value of a certain topological parameter of the graph. Our results can be extended to n -vertex digraphs of genus O(n 1-e ) for any e>0 . The problem of processing shortest pa th queries in graphs arises in application areas such as intelligent t ranspor ta t ion system (ITS), geographic information system (GIS), and robotics. In this paper, we present an efficient algorithmic solution for processing shortest pa th queries in undirected planar graphs with non-negative edge weights. Previous algorithms for this problem on planar graphs all have a tradeoff between the query t ime and the da ta structure space used by the solutions. The previously best known trade-off on an n-vertex planar graph G in the worst case is O(v -r) t ime for a pa th length query and O(v -r + L) t ime for report ing an actual shortest path, with a da ta structure of O(n2 x ) space, where r is an integer parameter with 1 < r _< n and L is the number of edges on the output shortest path. We present a new scheme, called frame search, that exploits the graph planari ty in a novel fashion. Wi th this scheme, we build an improved da ta structure of O(n + pv -r + p2 r) space (in O(n + p2 v + pr 3 4) time), where p is the minimum cardinality of a face-covering of the planar embedding of G with 1 < p < O(n), and r is an integer parameter with 1 < r < p. This da ta structure enables us to process each length query in O(v -rlog r + a(n)) t ime and report an actual shortest path in an addit ional O(L) time, where a(n) is the inverse of Ackermann's function. In the worst case, our approach reduces the previously best query t ime by a factor of up to O(n 1 4) if the same amount of space is used. Our technique can also be applied to improve the previous query algorithms for some geometric shortest pa th problems on the plane.