Bounded geometries, fractals, and low-distortion embeddings Anupam Gupta Robert Krauthgamer James R. Lee 10.1184/R1/6603941.v1 https://kilthub.cmu.edu/articles/journal_contribution/Bounded_geometries_fractals_and_low-distortion_embeddings/6603941 The doubling constant of a metric space (X, d) is the smallest value λ such that every ball in X can be covered by λ balls of half the radius. The doubling dimension of X is then defined as dim (X) = log2λ. A metric (or sequence of metrics) is called doubling precisely when its doubling dimension is bounded. This is a robust class of metric spaces which contains many families of metrics that occur in applied settings. We give tight bounds for embedding doubling metrics into (low-dimensional) normed spaces. We consider both general doubling metrics, as well as more restricted families such as those arising from trees, from graphs excluding a fixed minor, and from snowflaked metrics. Our techniques include decomposition theorems for doubling metrics, and an analysis of a fractal in the plane according to T. J. Laakso (2002). Finally, we discuss some applications and point out a central open question regarding dimensionality reduction in L2. 2006-03-01 00:00:00 computer sciences