Computing $L_{\mathrm{\infty }}$ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness

Our first question concerns the fine-grained complexity of the algorithmically most studied variant, the (continuous) directed Hausdorff distance under translation. The currently best upper bounds are $O(nm\log nm)$ for $d\le 2$ [11], $O({(nm)}^{d/2}\log nm)$ for $d=3$ [10]²²2While [10] only considers the case $m=n$, their analysis also holds for distinct $n,m$. A short explanation of their approach can also be found in the full version., and $O({(nm)}^{d/2}{(\log \log nm)}^{O(1)})$ for general $d\ge 4$ [9]. This suggests the following question:

Question 1: Is ${(nm)}^{d/2\pm o(1)}$ the time complexity of directed Hausdorff $L_{\mathrm{\infty }}$-distance under Translation?

A conditional lower bound of Bringmann and Nusser [7] (based on the Orthogonal Vectors Hypothesis) answers this question positively for $d=2$. Subsequently, Chan [9] gave evidence of optimality even for $d\ge 3$, by proving a conditional lower bound of ${(nm)}^{d/2-o(1)}$ for combinatorial algorithms³³3Here, combinatorial algorithms refers to algorithms that avoid the use of algebraic techniques underlying fast matrix multiplication algorithms beating $n^{3-o(1)}$ running time. in the case that $m\le n$. However, proving such a conditional lower bound against general algorithms for $d\ge 3$ (or better conditional lower bounds than ${(nm)}^{1-o(1)}$ for the case $n\ll m$) remained open until this work. Furthermore, for $d=1$, no $\tilde{O}(n+m+{(nm)}^{d/2})=\tilde{O}(n+m)$ algorithms are known, raising the question whether any superlinear lower bound can be proven for $d=1$.

As our first main contribution, we give a perhaps surprising negative answer to Question 1: For $d=3$ and $n=m^{o(1)}$, there exists an almost-linear time $m^{1+o(1)}$ algorithm, showing that in an unbalanced setting, the upper bound of $\tilde{O}({(nm)}^{d/2})$ can indeed be beaten (Section 3.4). Interestingly, this stands in contrast to the case of moderately small $m$: For $d=3$ and any $m\le \sqrt{n}$ we prove a tight conditional lower bound of ${(nm)}^{d/2-o(1)}$, by combining the proof techniques of Chan’s combinatorial $k$-clique lower bound [9] and the tight 3-uniform hyperclique lower bound for Klee’s measure problem in 3D [19] (Section 3.2). This reveals that the time complexity of the directed Hausdorff distance under translation is inherently asymmetric in $n$ and $m$ and breaks with tradition for algorithmic results on the Hausdorff distance under translation.

We investigate the case of small $n$ further and observe that our algorithmic approach could plausibly generalize to an $\tilde{O}(n^{d+1}{m}^{\lfloor d/2\rfloor })$ algorithm (we elaborate on the missing ingredient in Section 3.4) – such an algorithm would beat the baseline algorithm for all odd $d$ and small values of $n$. We also show that such an algorithm would indeed be conditionally tight: we also prove a corresponding lower bound of $m^{\lfloor d/2\rfloor -o(1)}$ for all $d\ge 4$, assuming the 3-uniform hyperclique hypothesis (Section 3.1).

Our conditional lower bounds can be adapted to the case of $n=\mathrm{\Theta }(m)$, but no longer match the upper bound. In fact, we obtain a conditional lower bound of $n^{2.25-o(1)}$ for $d=3$ which still leaves a gap of $n^{0.75\pm o(1)}$ to the upper bound of $\tilde{O}(n^3)$. It remains an open problem to settle the full time complexity for any relationship between $n$ and $m$. An intriguing possibility consistent with our results is the existence of an $\tilde{O}(n^{\lceil d/2\rceil }{m}^{\lfloor d/2\rfloor })$-time algorithm.

We turn to our second main question.

Question 2: How does the choice of dimension, directed vs. undirected and discrete vs. continuous affect the time complexity?

We observe that the time complexity of computing Hausdorff distances under translation exhibits an intricate interplay between the different aspects of the problem, illustrated in Table 1 and Figure 1.

For clarity of presentation, it is often useful to view the Hausdorff under Translation decision problem as a translation problem involving certain shapes.

For an instance of HuT with point sets $P,Q$ and $\delta >0$, if we construct hypercubes $𝒬$ with side length $2\delta$ and centers $q\in Q$, the region $T^{\ast }={\bigcap }_{p\in P}{\bigcup }_{\widehat{Q}\in 𝒬}\widehat{Q}-p$ is exactly the region of feasible translations, i.e., we have $\tau \in T^{\ast }\iff \forall p\in P\exists q\in Q:{\delta }_{\overrightarrow{H}}(P+\tau ,Q)\le \delta$ [1]. We call this case, where all shapes $𝒬$ are hypercubes of the same size, the Translation Problem with Hypercubes (TPwC). In case all shapes of $Q$ are axis-aligned boxes (of arbitrary size), we call it the Translation Problem with Boxes (TPwB). While the TPwC problem is equivalent to HuT, there is no reduction to HuT known within the same ambient space from the Translation Problem with Boxes or even from the translation problem with hypercubes of different sizes. We further use a third variant.

We call the shapes of the TPwO instance, i.e., the shapes of its sub-instances, orthants as within the target box all hypercubes are indistinguishable from orthants. An important property of this problem, which we will use later, is that we may fix the side-length of all orthants to a value $\delta >{\delta }_0$. Similar to [9, Lemma 3], the TPwO problem reduces to the TPwC and thus has a reduction to HuT, its proof is deferred to the full version. A converse reduction, from HuT to TPwO, is generally not known.

For our lower bounds in higher dimensions ($d\ge 4$), we give a reduction in three steps from the $k$-hyperclique problem to HuT, see the full version for a formal definition and its hardness hypothesis.

In the first step, we encode any $k$-tuple of vertices of a hypergraph $H=(V,E)$ as cells inside a $\lfloor d/2\rfloor$-dimensional hypercube, see Figure 2. The used encoding was introduced by Chan [9]. For any non-edge $\overline{e}\in \left(\genfrac{}{}{0pt}{}{V}{3}\right)\setminus E$, the feasible region of $\overline{e}$ are the cells inside the hypercube for which the corresponding $k$-tuple does not include $\overline{e}$. In contrast, the cells for which the corresponding $k$-tuple includes all vertices of $\overline{e}$ are called the forbidden region. For each non-edge, we construct a covering of its feasible region with axis-aligned boxes⁶⁶6As we only consider axis-aligned boxes in this paper, we may only call these boxes., see Lemma 3.5 for the exact covering. As a $k$-clique is a $k$-tuple which does not contain any non-edge, a cell that lies within the feasible regions of all non-edges encodes a $k$-clique. In Lemma 3.6 we reduce finding a cell inside all feasible regions to the intermediate Translated Box-Shape Problem (Definition 3.2) with our desired values of $n,m$.

In the second step, the resulting Translated Shape Problem is reduced to the Translation Problem with Boxes, see Lemma 3.3.

Lastly, in our third step we reduce the Translation Problem with Boxes in $\lfloor d/2\rfloor$-D to the Translation Problem with Orthants in $d$ dimensions with $n$ points and $m$ orthants, see Lemma 3.1. As given in Lemma 2.6, the Translation Problem with Orthants has a linear time reduction to directed Hausdorff under Translation, which yields our lower bound.

We go through the steps in backwards order, starting with the last, third step.

Chan [9] has proven a tight lower bound that applies for distributions $m\in O(n)$ in $3$-D. We give a non-combinatorial version of this ${(nm)}^{d/2-o(1)}$ lower bound for $m\in O(n^{1/2})$.

We reduce from the $k$-Hyperclique problem, combining Chan’s ideas with the work of Künnemann [19] using prefix covering designs. As done in Section 3.1, we encode a $k$-tuple of vertices inside a $d$-dimensional hypercube. However, we use a redundant encoding based on the prefix covering designs, that is, each color class is encoded more than once to our hypercube. The full proof is presented in the full version.

We draw several connections between the Hausdorff distance under Translation and several additive problems. Below we highlight a conditional lower bound in 1D and conditional upper bound in 3D. Omitted proofs and additional results are given in the full version.

We first show that even for one-dimensional instances, directed HuT inherits hardness from quadratic-time barriers from problems such as MaxConv LowerBound.

In an investigation of hardness results from $(\min ,+)$-convolution, Cygan, Mucha, Wegrzycki and Wlodarczyk [12] studied the closely related MaxConv LowerBound problem and gave a subquadratic reduction to $L_{\mathrm{\infty }}$-Necklace Alignment (in turn, $L_{\mathrm{\infty }}$-Necklace Alignment admits a subquadratic reduction to $(\min ,+)$-Convolution [6]). Cygan et al. raised the natural question whether MaxConv LowerBound is subquadratic equivalent to $(\min ,+)$-convolution; to the best of our knowledge, neither a positive or negative resolution is known.

For the (continuous) directed HuT we get hardness by a reduction from the Linear Alignment problem, shown in the full version. Further, using a reduction from $L_{\mathrm{\infty }}$-Necklace Alignment to Linear Alignment, we get a reduction from MaxConv LowerBound to directed HuT. Interestingly, we obtain such a lower bound even for discrete directed HuT by directly reducing from MaxConv LowerBound. These reductions illuminate why no subquadratic algorithms are known for directed variants, despite near-linear algorithms for their undirected counterparts [20].

For $n=m^{o(1)}$, Theorem 3.7 gives a ${(nm)}^{\lfloor d/2\rfloor -o(1)}$ lower bound, which for even $d$ matches the best known algorithm running in time $O({(nm)}^{d/2})$ [9], while for odd $d$ it seems to have some slack. Intuitively, one might expect that the known ${(nm)}^{d/2-o(1)}$ combinatorial lower bound for $m=O(n)$ [9] also transfers to the case of $m\gg n$. Surprisingly, in $3$-D the ${(nm)}^{1-o(1)}$ lower bound of [7] is tight for $n=m^{o(1)}$ as we give an $O(m^{1+o(1)})$ algorithm.

The algorithm uses a structural insight from [10, Theorem 7], which we turn algorithmic. The full description and proof can be found in the full version. Our algorithm relies on an algorithm recently introduced by Agarwal and Steiger [2], which in $3$-D computes the vertices of the union of $m$ unit cubes in an output-sensitive runtime of $\tilde{O}(m)$. Assuming an algorithm that computes the vertices of the union of $m$ unit hypercubes in $d$-D in time $\tilde{O}(m^{\lfloor d/2\rfloor })$, our algorithm directly generalizes to higher dimensions with a runtime of $\tilde{O}(m^{\lfloor d/2\rfloor }{n}^{d+1})$.

Its existence forbids ${(nm)}^{d/2-o(1)}$ lower bounds for arbitrary distributions of $n,m$ for $d=3$, and we give compelling intuition for a similar result in odd $d>3$.

This result points to a discrepancy in complexity, at least for $d=3$ but potentially also for all odd $d$. While we have a $\tilde{O}(m)$ algorithm for $n=m^{o(1)}$, there is a ${(nm)}^{d/2-o(1)}$ tight (combinatorial) lower bound for $m\in O(n)$ [9]. It remains unknown where the cutoff point is located, i.e., for which values of $n,m$ do we start to get faster than ${(nm)}^{d/2\pm o(1)}$ algorithms?

As of now, all here presented lower bounds only apply to the directed Hausdorff under Translation setting. Chan [9] already raised the question if these bounds transfer to the undirected setting, however there are no such lower bounds known so far for $d\ge 3$. Only for $d=2$, lower bounds for the undirected setting are known [7], which match the bounds for the directed variant. For $d=1$, we have an optimal $\tilde{O}(n+m)$ algorithm [20].

We partially resolve this question by providing a reduction from the Translation Problem with Orthants to undirected Hausdorff under Translation, maintaining all instance parameters.