  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 + \varepsilon)$-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 +
\varepsilon)$-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.
