@online{Bringmann_2101.07696,
TITLE = {Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation},
AUTHOR = {Bringmann, Karl and Nusser, Andr{\'e}},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2101.07696},
EPRINT = {2101.07696},
EPRINTTYPE = {arXiv},
YEAR = {2021},
ABSTRACT = {Computing the similarity of two point sets is a ubiquitous task in medical<br>imaging, geometric shape comparison, trajectory analysis, and many more<br>settings. Arguably the most basic distance measure for this task is the<br>Hausdorff distance, which assigns to each point from one set the closest point<br>in the other set and then evaluates the maximum distance of any assigned pair.<br>A drawback is that this distance measure is not translational invariant, that<br>is, comparing two objects just according to their shape while disregarding<br>their position in space is impossible.<br> Fortunately, there is a canonical translational invariant version, the<br>Hausdorff distance under translation, which minimizes the Hausdorff distance<br>over all translations of one of the point sets. For point sets of size $n$ and<br>$m$, the Hausdorff distance under translation can be computed in time $\tilde<br>O(nm)$ for the $L_1$ and $L_\infty$ norm [Chew, Kedem SWAT'92] and $\tilde O(nm<br>(n+m))$ for the $L_2$ norm [Huttenlocher, Kedem, Sharir DCG'93].<br> As these bounds have not been improved for over 25 years, in this paper we<br>approach the Hausdorff distance under translation from the perspective of<br>fine-grained complexity theory. We show (i) a matching lower bound of<br>$(nm)^{1-o(1)}$ for $L_1$ and $L_\infty$ assuming the Orthogonal Vectors<br>Hypothesis and (ii) a matching lower bound of $n^{2-o(1)}$ for $L_2$ in the<br>imbalanced case of $m = O(1)$ assuming the 3SUM Hypothesis.<br>},
}