Planar earthmover is not in L1

Assaf Naor; Gideon Schechtman

doi:10.1137/05064206X

Planar earthmover is not in L₁

Assaf Naor
, Gideon Schechtman

Research output: Contribution to journal › Article › peer-review

74 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	804-826
Number of pages	23
Journal	SIAM Journal on Computing
Volume	37
Issue number	3
DOIs	https://doi.org/10.1137/05064206X
State	Published - 2007
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Keywords

Earthmover metric
Metric embeddings
Nearest neighbor search

Access to Document

10.1137/05064206X

Cite this

@article{47430ce43e674445bfe9666d5811376f,

title = "Planar earthmover is not in L1",

abstract = "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).",

keywords = "Earthmover metric, Metric embeddings, Nearest neighbor search",

author = "Assaf Naor and Gideon Schechtman",

year = "2007",

doi = "10.1137/05064206X",

language = "English (US)",

volume = "37",

pages = "804--826",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Planar earthmover is not in L1

AU - Naor, Assaf

AU - Schechtman, Gideon

PY - 2007

Y1 - 2007

N2 - 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).

AB - 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).

KW - Earthmover metric

KW - Metric embeddings

KW - Nearest neighbor search

UR - https://www.scopus.com/pages/publications/46449112099

UR - https://www.scopus.com/pages/publications/46449112099#tab=citedBy

U2 - 10.1137/05064206X

DO - 10.1137/05064206X

M3 - Article

AN - SCOPUS:46449112099

SN - 0097-5397

VL - 37

SP - 804

EP - 826

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -