On Epsilon-Nets, Distance Oracles, and Metric Embeddings
  We give two new applications of an observation from \cite{ADFGW11}. The first is an almost linear sized constant time data structure for reporting very large distances in undirected graphs. The second is a generic transformation of results about $\ell_1$-embeddability of metrics to a setting, where we are interested in preservation of large distances only. 
Ilya Razenshteyn
cs.DS math.CO math.MG