Optimal (Euclidean) Metric Compression
Optimal (Euclidean) Metric Compression
We study the problem of representing all distances between $n$ points in ${\mathbb R}^d$, with arbitrarily small distortion, using as few bits as possible. We give asymptotically tight bounds for this problem, for Euclidean metrics, for $\ell_1$ (also known as Manhattan)-metrics, and for general metrics. Our bounds for Euclidean metrics …