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

arXiv: https://arxiv.org/abs/2104.08136 · HTML: https://mlsanity.com/paper/2104.08136/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2021.

## Built on by (most cited first, 1 of 1)

- [Digger: Detecting Copyright Content Mis-usage in Large Language Model Training](https://mlsanity.com/paper/2401.00676/) (2024)

## Abstract (arXiv)

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.