Item

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 $\tilde
O(nm)$ for the $L_1$ and $L_\infty$ norm [Chew, Kedem SWAT'92] and $\tilde O(nm
(n+m))$ for the $L_2$ 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_1$ and $L_\infty$ assuming the Orthogonal Vectors
Hypothesis and (ii) a matching lower bound of $n^{2-o(1)}$ for $L_2$ in the
imbalanced case of $m = O(1)$ assuming the 3SUM Hypothesis.