Oliver Klein Institut für Informatik Freie Universität Berlin email: oklein@inf.fu-berlin.de
Remco C. Veltkamp Department of Computer Science Utrecht University email: remco.veltkamp@cs.uu.nl
Report B 05-11
July 2005
Abstract
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: Server: fubinf.inf.fu-berlin.de File: pub/reports/tr-b-05-11.ps.gz