On Epsilon-Nets, Distance Oracles, and Metric Embeddings

Abstract

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.

7 pages