Volume distortion for subsets of Euclidean spaces
James R. Lee · 2006
In [Rao 1999], it is shown that every n-point Euclidean metric with polynomial aspect ratio admits a Euclidean embedding with k-dimensional distortion bounded by O ( √ log n log k), a result which is tight for constant values of k. We show that this holds without any assumption on the aspect ratio, and give an improved bound of O ( √ log n(log k) 1/4). Our main result is an upper bound of O ( √ log n log log n) independent of the value of k, nearly resolving the main open questions of [Dunagan-Vempala 2001] and [Krauthgamer-Linial-Magen 2004]. The best previous bound was O(log n), and our bound is nearly tight, as even the 2-dimensional volume distortion of an n-vertex path is Ω ( √ log n). 1