License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.18
URN: urn:nbn:de:0030-drops-138177
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13817/
Bringmann, Karl ;
Nusser, André
Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation
Abstract
Computing the similarity of two point sets is a ubiquitous task in medical imaging, geometric shape comparison, trajectory analysis, and many more settings. Arguably the most basic distance measure for this task is the Hausdorff distance, which assigns to each point from one set the closest point in the other set and then evaluates the maximum distance of any assigned pair. A drawback is that this distance measure is not translational invariant, that is, comparing two objects just according to their shape while disregarding their position in space is impossible.
Fortunately, there is a canonical translational invariant version, the Hausdorff distance under translation, which minimizes the Hausdorff distance over all translations of one of the point sets. For point sets of size n and m, the Hausdorff distance under translation can be computed in time ?̃(nm) for the L₁ and L_∞ norm [Chew, Kedem SWAT'92] and ?̃(nm (n+m)) for the L₂ norm [Huttenlocher, Kedem, Sharir DCG'93].
As these bounds have not been improved for over 25 years, in this paper we approach the Hausdorff distance under translation from the perspective of fine-grained complexity theory. We show (i) a matching lower bound of (nm)^{1-o(1)} for L₁ and L_∞ assuming the Orthogonal Vectors Hypothesis and (ii) a matching lower bound of n^{2-o(1)} for L₂ in the imbalanced case of m = ?(1) assuming the 3SUM Hypothesis.
BibTeX - Entry
@InProceedings{bringmann_et_al:LIPIcs.SoCG.2021.18,
author = {Bringmann, Karl and Nusser, Andr\'{e}},
title = {{Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {18:1--18:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13817},
URN = {urn:nbn:de:0030-drops-138177},
doi = {10.4230/LIPIcs.SoCG.2021.18},
annote = {Keywords: Hausdorff Distance Under Translation, Fine-Grained Complexity Theory, Lower Bounds}
}
|
Keywords: |
|
Hausdorff Distance Under Translation, Fine-Grained Complexity Theory, Lower Bounds |
|
Collection: |
|
37th International Symposium on Computational Geometry (SoCG 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.06.2021 |
