Planar earthmover is not in L1

Assaf Naor, Gideon Schechtman

Research output: Contribution to journalArticlepeer-review


We show that any L1 embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid {0,1,..., n}2 ⊆ ℝ2 incurs distortion Ω (√log n). We also use Fourier analytic techniques to construct a simple L1 embedding of this space which has distortion O(log n).

Original languageEnglish (US)
Pages (from-to)804-826
Number of pages23
JournalSIAM Journal on Computing
Issue number3
StatePublished - 2007


  • Earthmover metric
  • Metric embeddings
  • Nearest neighbor search

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Planar earthmover is not in L1'. Together they form a unique fingerprint.

Cite this