Approximating the Earth Mover's Distance between sets of geometric objects

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.