Fine-Grained Complexity of Earth Mover’s Distance Under Translation
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2024-06
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
40th International Symposium on Computational Geometry, SoCG 2024, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 293
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 (EMDuT) is a translation-invariant version thereof. It minimizes the Earth Mover’s Distance over all translations of one point set. For EMDuT in R1, we present an Oe(n2)-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 EMDuT in Rd, we present an Oe(n2d+2)-time algorithm for the L1 and L∞ metric. We show that this dependence on d is asymptotically tight, as an no(d)-time algorithm for L1 or L∞ would contradict the Exponential Time Hypothesis (ETH). Prior to our work, only approximation algorithms were known for these problems.Description
Publisher Copyright: © Karl Bringmann, Frank Staals, Karol Węgrzycki, and Geert van Wordragen.
Keywords
Earth Mover’s Distance, Earth Mover’s Distance under Translation, Fine-Grained Complexity, Maximum Weight Bipartite Matching
Other note
Citation
Bringmann, K, Staals, F, Węgrzycki, K & van Wordragen, G 2024, Fine-Grained Complexity of Earth Mover’s Distance Under Translation. in W Mulzer & J M Phillips (eds), 40th International Symposium on Computational Geometry, SoCG 2024., 25, Leibniz International Proceedings in Informatics, LIPIcs, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Computational Geometry, Athens, Greece, 11/06/2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.25