Volume Distortion for Subsets of Euclidean Spaces
In Rao (Proceedings of the 15th Annual Symposium on Computational Geometry, pp. 300-306, 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(root 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 (root log n (log k)(1/4)). Our main result is an upper bound of O (root log n log log n) independent of the value of k, nearly resolving the main open questions of Dunagan and Vempala (Randomization, Approximation, and Combinatorial Optimization, pp. 229-240, 2001) and Krauthgamer et al. (Discrete Comput. Geom. 31(3):339-356, 2004). The best previous bound was O(log n), and our bound is nearly tight, as even the two-dimensional volume distortion of an n-vertex path is ohm (root log n).
finite metric spaces approximation algorithms bi-lipschitz geometry