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

## Abstract

Given two distributions $$P$$ and $$S$$ of equal total mass, the Earth Mover’s Distance measures the cost of transforming one distribution into the other, where the cost of moving a unit of mass is equal to the distance over which it is moved.

We give approximation algorithms for the Earth Mover’s Distance between various sets of geometric objects. We give a $$(1 + \eps)$$-approximation when $$P$$ is a set of weighted points and $$S$$ is a set of line segments, triangles or $$d$$-dimensional simplices. When $$P$$ and $$S$$ are both sets of line segments, sets of triangles or sets of simplices, we give a $$(1 + \eps)$$-approximation with a small additive term. All algorithms run in time polynomial in the size of $$P$$ and $$S$$, and actually calculate the transport plan (that is, a specification of how to move the mass), rather than just the cost. To our knowledge, these are the first combinatorial algorithms with a provable approximation ratio for the Earth Mover’s Distance when the objects are continuous rather than discrete points.

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

CoRR, 2021

@article{emd2021,
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},
year = {2021},
category = {other},
journal = {CoRR},
volume = {abs/2104.08136},
url = {https://arxiv.org/abs/2104.08136},
}


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

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},
}