Fine-Grained Complexity of Earth Mover's Distance under Translation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918204392079360 |
|---|---|
| author | Bringmann, Karl Staals, Frank Węgrzycki, Karol van Wordragen, Geert |
| author_facet | Bringmann, Karl Staals, Frank Węgrzycki, Karol van Wordragen, Geert |
| contents | 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 $\tilde{\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 $\tilde{\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04356 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fine-Grained Complexity of Earth Mover's Distance under Translation Bringmann, Karl Staals, Frank Węgrzycki, Karol van Wordragen, Geert Computational Geometry 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 $\tilde{\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 $\tilde{\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. |
| title | Fine-Grained Complexity of Earth Mover's Distance under Translation |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2403.04356 |