Approximating the Earth Mover’s Distance between a set of points and line segments

Abstract

We show that a \((1 + \eps)\)-approximation algorithm exists for the Earth Mover’s Distance between a set of \(n\) points and set of \(n\) line segments with equal total weight. Our algorithm runs in \(O\left(\frac{n^6}{\eps^2} \log^2 \left(\frac{1}{\eps}\right) \log^2 \left(\frac{n^2}{\eps} \log \frac{1}{\eps} \right)\right)\) time.

Corresponding Publications

Approximating the Earth Mover’s Distance between a set of points and line segments

Marc van Kreveld, Frank Staals, Amir Vaxman, Jordi L. Vermeulen

Abstr. 35th European Workshop on Computational Geometry (EuroCG), 2019

@article{emd_eurocg,
  author = {van Kreveld, Marc and Staals, Frank and Vaxman, Amir and Vermeulen, Jordi L.},
  title = {Approximating the Earth Mover's Distance between a set of points and line segments},
  journal = {Abstr. 35th European Workshop on Computational Geometry (EuroCG)},
  year = {2019},
  location = {Utrecht, The Netherlands},
  numpages = {6},
  category = {other},
  url = {http://www.eurocg2019.uu.nl/papers/24.pdf},
  project = {emd2021},
}