Abstract

The Earth Mover’s Distance is a popular similarity measure in several branches of computer science. It measures the minimum total edge length of a perfect matching between two point sets. The Earth Mover’s Distance under Translation (\(\mathrm{EMDuT}\)) is a translation-invariant version thereof. It minimizes the Earth Mover’s Distance over all translations of one point set.

For \(\mathrm{EMDuT}\) in \(\mathbb{R}^1\), we present an \(\widetilde{\mathcal{O}}(n^2)\)-time algorithm. We also show that this algorithm is nearly optimal by presenting a matching conditional lower bound based on the Orthogonal Vectors Hypothesis. For \(\mathrm{EMDuT}\) in \(\mathbb{R}^d\), we present an \(\widetilde{\mathcal{O}}(n^{2d+2})\)-time algorithm for the \(L_1\) and \(L_\infty\) metric. We show that this dependence on \(d\) is asymptotically tight, as an \(n^{o(d)}\)-time algorithm for \(L_1\) or \(L_\infty\) would contradict the Exponential Time Hypothesis (ETH). Prior to our work, only approximation algorithms were known for these problems.

Corresponding Publications

Fine-Grained Complexity of Earth Mover’s Distance under Translation

Karl Bringmann, Frank Staals, Karol Węgrzycki, Geert van Wordragen

Proc. 40th Annual Symposium on Computational Geometry, 2024

Download Local Copy View Slides Export Citation

@inproceedings{emdut2024,
  author = {Bringmann, Karl and Staals, Frank and W\k{e}grzycki, Karol and van Wordragen, Geert},
  title = {Fine-Grained Complexity of Earth Mover's Distance under Translation},
  booktitle = {Proc. 40th Annual Symposium on Computational Geometry},
  year = {2024},
  location = {Athens, Greece},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  category = {other},
  doi = {4230/LIPIcs.SoCG.2024.25},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2024.25},
  volume = {293},
  pages = {25:1--25:17},
}