Computing $L_infty$ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness

arXiv:2603.08890v1 Announce Type: new
Abstract: To measure the shape similarity of point sets, various notions of the Hausdorff distance under translation are widely studied. In this context, for an $n$-point set $P$ and $m$-point set $Q$ in $mathbb{R}^d$, we consider the task of computing the minimum $d(P,Q+tau)$ over translations $tau in T$, where $d(cdot, cdot)$ denotes the Hausdorff distance under the $L_infty$-norm. We analyze continuous ($T=mathbb{R}^d$) vs. discrete ($T$ is finite) and directed vs. undirected variants. Applying fine-grained complexity, we analyze running time dependencies on dimension $d$, the $n$ vs. $m$ relationship, and the chosen variant. Our main results are: (1) The continuous directed Hausdorff distance has asymmetric time complexity. While (Chan, SoCG’23) gave a symmetric $tilde{O}((nm)^{d/2})$ upper bound for $dge 3$, which is conditionally optimal for combinatorial algorithms when $m le n$, we show this fails for $n ll m$ with a combinatorial, almost-linear time algorithm for $d=3$ and $n=m^{o(1)}$. We also prove general conditional lower bounds for $dge 3$: $m^{lfloor d/2 rfloor -o(1)}$ for small $n$, and $n^{d/2 -o(1)}$ for $d=3$ and small $m$. (2) While lower bounds for $d ge 3$ hold for directed and undirected variants, $d=1$ yields a conditional separation. Unlike undirected variants solvable in near-linear time (Rote, IPL’91), we prove directed variants are at least as hard as the additive MaxConv LowerBound (Cygan et al., TALG’19). (3) The discrete variant reduces to a 3SUM variant for $dle 3$. This creates a barrier to proving tight lower bounds under the Orthogonal Vectors Hypothesis (OVH), contrasting with continuous variants that admit tight OVH-based lower bounds in $d=2$ (Bringmann, Nusser, JoCG’21). These results reveal an intricate interplay of dimensionality, symmetry, and discreteness in computing translational Hausdorff distances.