Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair

We give a reduction from $(1+\epsilon)$-approximate Earth Mover's Distance (EMD) to $(1+\epsilon)$-approximate Closest Pair. As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given $p\in [1, 2]$ and two sets of $n$ points $X,Y \subset (\R^d,\ell_p)$, their EMD is the minimum cost of a perfect matching between $X$ and $Y$, where the cost of matching two vectors is their $\ell_p$ distance. Further, Closest Pair is the basic problem of finding a pair of points realizing $\min_{x \in X, y\in Y} ||x-y||_p$.