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

We give a reduction from (1+varepsilon)-approximate Earth Mover's Distance (EMD) to (1+varepsilon)-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given p∈ [1, 2] and two sets of n points X,Y subseteq (mathbb Rd,ℓp), their EMD is the minimum cost of a perfect matching between X and Y, where the cost of matching two vectors is their ℓp distance. Further, CP is the basic problem of finding a pair of points realizing minx ∈ X, y∈ Y ||x-y||p. Our contribution is twofold: we show that if a (1+varepsilon)-approximate CP can be computed in time n2-φ, then a 1+O(varepsilon) approximation to EMD can be computed in time n2-Omega(φ); plugging in the fastest known algorithm for CP [Alman, Chan, Williams FOCS'16], we obtain a (1+varepsilon)-approximation algorithm for EMD running in time n^2-tildeOmega(varepsilon1/3) for high-dimensional point sets, which improves over the prior fastest running time of n2-Omega(varepsilon2) [Andoni, Zhang FOCS'23]. Our main technical contribution is a sublinear implementation of the Multiplicative Weights Update framework for EMD. Specifically, we demonstrate that the updates can be executed without ever explicitly computing or storing the weights; instead, we exploit the underlying geometric structure to perform the updates implicitly.