# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2101.07696.pdf

(Preprint), 778KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bringmann, K., & Nusser, A. (2021). Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. Retrieved from https://arxiv.org/abs/2101.07696.

Cite as: https://hdl.handle.net/21.11116/0000-0008-E242-E

##### 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.

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.