• DocumentCode
    2914270
  • Title

    Planar Earthmover is not in L_1

  • Author

    Naor, Assaf ; Schechtman, Gideon

  • fYear
    2006
  • fDate
    Oct. 2006
  • Firstpage
    655
  • Lastpage
    666
  • 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 sube Ropf2 incurs distortion Omega(radic;(log n)). We also use Fourier analytic techniques to construct a simple L1 embedding of this space which has distortion O(log n)
  • Keywords
    Fourier analysis; computational complexity; computational geometry; probability; Fourier analytic technique; planar Earthmover; probability; transportation cost metric; Computer graphics; Computer science; Computer vision; Cost function; Distortion measurement; Extraterrestrial measurements; Labeling; Nearest neighbor searches; Probability distribution; Transportation;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 2006. FOCS '06. 47th Annual IEEE Symposium on
  • Conference_Location
    Berkeley, CA
  • ISSN
    0272-5428
  • Print_ISBN
    0-7695-2720-5
  • Type

    conf

  • DOI
    10.1109/FOCS.2006.60
  • Filename
    4031400
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2914270