Bounded geometries, fractals, and low-distortion embeddings

Anupam Gupta, Robert Krauthgamer, James R. Lee

Research output: Contribution to journalConference articlepeer-review


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 due to Laakso [21]. Finally, we discuss some applications and point out a central open question regarding dimensionality reduction in L2.

Original languageEnglish (US)
Pages (from-to)534-543
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 2003
EventProceedings: 44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003 - Cambridge, MA, United States
Duration: Oct 11 2003Oct 14 2003

ASJC Scopus subject areas

  • Hardware and Architecture
  • General Computer Science


Dive into the research topics of 'Bounded geometries, fractals, and low-distortion embeddings'. Together they form a unique fingerprint.

Cite this