Bounded geometries, fractals, and low-distortion embeddings

摘要: The doubling constant of a metric space (X, d) is the smallest value /spl lambda/ such that every ball in X can be covered by balls half radius. dimension then defined as dim (X) = log/sub 2//spl lambda/. A (or sequence metrics) called precisely when its bounded. This robust class spaces which contains many families metrics occur applied settings. We give tight bounds for embedding into (low-dimensional) normed spaces. consider both general metrics, well more restricted those arising from trees, graphs excluding fixed minor, and snowflaked metrics. Our techniques include decomposition theorems an analysis fractal plane according to T. J. Laakso (2002). Finally, we discuss some applications point out central open question regarding dimensionality reduction L/sub 2/.