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.