text: 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).
  @cite_14: Novel amorphous copolymers of mono-olefins or of mono-olefins and non-conjugated dienes with unsaturated derivatives of imides, are disclosed. These copolymers containing from 99.9 to 80 by weight of non-polar units derived from at least two mono-olefins containing 2 to 18 carbon atoms, particularly ethylene and propene or ethylene and butene-1, and possibly one or more non-conjugated dienes, and from 0.1 to 20 units derived from an amide having the formula: wherein:
  @cite_0: 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).
  @cite_15: 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.
  @cite_10: 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.
  @cite_12: 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].
  @cite_11: 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.
summary: 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 .