Approximation Algorithms for the Earth Mover's Distance Under Transformations Using Reference Points

Oliver Klein Institut für Informatik Freie Universität Berlin email:

Remco C. Veltkamp Department of Computer Science Utrecht University email:

Report B 05-11
July 2005

The Earth Mover's Distance (EMD) on weighted point sets is a distance measure with many applications. Since there are no known exact algorithms to compute the minimum EMD under transformations, it is useful to estimate the minimum EMD under various classes of transformations. For weighted point sets in the plane, we will show a $2$-approximation algorithm for translations, a $4$-approximation algorithm for rigid motions and an $8$-approximation algorithm for similarity operations. The runtime of the translation approximation is $O(T^{EMD}(n,m))$, the runtime of the latter two algorithms is $O(nm T^{EMD}(n,m))$, where $T^{EMD}(n,m)$ is the time to compute the EMD between two weighted point sets with $n$ and $m$ points, respectively. We will also show that these algorithms can be extended to arbitrary dimension, giving higher worse time and approximation bounds, however. All these algorithms are based on a more general structure, namely on reference points, which lead to the elegant generalizations to higher dimensions. We give a comprehensive discussion of reference points for weighted point sets with respect to the EMD. Finally, we will extend our discussion to a variant of the EMD, namely the Proportional Transportation Distance (PTD) and we will show similar results.

Get the report here or by anonymous ftp:
File: pub/reports/