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

This paper employs fine-grained complexity to analyze the computational hardness of minimizing the $L_\infty$ Hausdorff distance under translation, revealing intricate dependencies on dimensionality, the directed versus undirected nature of the distance, and the choice between continuous and discrete translation spaces, including asymmetric time complexities and conditional lower bounds that distinguish these variants.

The Gist

Imagine you have two scattered groups of people in a large, empty room. One group is wearing red shirts (Set P), and the other is wearing blue shirts (Set Q).

Your goal is to find the best way to move the red group so that they match up as closely as possible with the blue group. But there's a catch: you don't just want them to be "close" in a general sense; you want to measure the worst-case distance. Specifically, you want to know: "What is the maximum distance any single red person has to walk to reach their nearest blue neighbor?" You want to minimize this maximum distance.

This is the Hausdorff Distance. It's a way to measure how similar two shapes are, even if they are shifted around.

This paper is a deep dive into the mathematical difficulty (complexity) of solving this problem when you are allowed to slide the red group anywhere in a multi-dimensional space (like 3D space, or even higher dimensions). The authors are asking: How fast can a computer solve this? Does it get harder if we have more people? Does it get harder if we add more dimensions? Does it matter if we care about matching everyone, or just the red people matching the blue ones?

Here is the breakdown of their findings using some everyday analogies:

1. The "One-Way" vs. "Two-Way" Street (Symmetry)

Usually, when we compare shapes, we care if they match perfectly in both directions (Red matches Blue, AND Blue matches Red). This is the Undirected version.
However, sometimes we only care if the Red group fits inside the Blue group's territory. This is the Directed version.

• The Surprise: In most math problems, if you can solve the "one-way" version, you can easily solve the "two-way" version. But here, the authors found a weird exception in 1-dimensional space (a straight line).
  • The Analogy: Imagine lining up two rows of dominoes. If you just want to make sure every domino in Row A has a neighbor in Row B, it's easy (fast). But if you also need to make sure every domino in Row B has a neighbor in Row A, it suddenly becomes a much harder puzzle, almost as hard as a specific type of complex math problem called "MaxConv."
  • The Takeaway: In 1D, the "one-way" check is surprisingly difficult, while the "two-way" check is easy. In higher dimensions (3D and up), they are roughly equally hard.

2. The "Unbalanced" Crowd (Dimensionality & Size)

The authors looked at what happens when the two groups are very different sizes.

• The Old Belief: For a long time, mathematicians thought that if you have $N$ red people and $M$ blue people, the time it takes to solve the puzzle was roughly proportional to $(N \times M)^{d/2}$ (where $d$ is the number of dimensions). They thought this rule applied no matter how unbalanced the groups were.
• The Discovery: The authors proved this rule is wrong when one group is tiny and the other is huge.
  • The Analogy: Imagine you are trying to fit a single tiny ant (Red) into a massive stadium filled with thousands of seats (Blue). The old math said you'd have to check every seat against the ant, which takes forever. The authors found a "shortcut." Because the ant is so small, you can use a clever trick to find the best seat in almost linear time (very fast).
  • The Takeaway: The difficulty of the problem is asymmetric. It depends heavily on which group is bigger. If the groups are balanced, it's hard. If one is tiny, it's surprisingly easy.

3. The "Discrete" vs. "Continuous" Slide

• Continuous: You can slide the red group by any amount, even a tiny fraction of a millimeter.

• Discrete: You can only slide the red group to specific, pre-defined spots (like stepping on tiles on a floor).

• The Discovery:

  • In 2D, the "Continuous" version is known to be very hard (based on a hypothesis called the Orthogonal Vectors Hypothesis).
  • However, for the "Discrete" version, the authors found a link to a famous problem called 3SUM (finding three numbers that add up to zero).
  • The Analogy: Think of the "Continuous" problem as trying to find a perfect spot on a smooth, infinite canvas. The "Discrete" problem is like trying to find a spot on a grid. The authors showed that for low dimensions (3D and under), the grid version is linked to the "3SUM" puzzle. This is a big deal because if you could solve the grid version super fast, you would also solve the 3SUM puzzle super fast, which most computer scientists believe is impossible.
  • The Takeaway: The "Discrete" version hits a "wall" (a barrier) that prevents us from proving it's as hard as the "Continuous" version using current methods. It suggests the grid version might be slightly easier or just different in nature.

4. The "Interplay" (The Big Picture)

The title mentions an "Interplay of Dimensionality, Symmetry, and Discreteness."

• Dimensionality: As you add more dimensions (go from 2D to 3D to 4D), the problem gets exponentially harder, but the "shortcut" for unbalanced groups still works in 3D.
• Symmetry: Whether you check "one-way" or "two-way" changes the difficulty, especially in 1D.
• Discreteness: Whether you are sliding on a smooth surface or a grid changes the type of mathematical "hardness" you hit.

Summary for the General Audience

This paper is like a map for computer scientists trying to solve a shape-matching puzzle. They discovered that:

1. Size matters: If one shape is tiny compared to the other, the puzzle is much easier than we thought.
2. Direction matters: In 1D, checking if "A fits in B" is actually harder than checking if "A and B fit each other."
3. Grids are tricky: Matching shapes on a grid (discrete) is linked to a different, famous hard problem (3SUM), making it hard to prove exactly how difficult it is compared to matching on a smooth surface (continuous).

The authors didn't just solve the puzzle; they mapped out exactly where the difficulty lies, showing that the rules of the game change depending on the size of the groups, the number of dimensions, and whether you are looking at a grid or a smooth surface.

Technical Summary

Here is a detailed technical summary of the paper "Computing L∞ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness" by Angrick et al.

1. Problem Definition

The paper investigates the computational complexity of measuring the similarity between two point sets, $P$ (size $n$) and $Q$ (size $m$), in $d$-dimensional space ($\mathbb{R}^d$) under translation. The goal is to find a translation vector $\tau$ from an admissible set $T$ that minimizes the Hausdorff distance.

The study focuses on the $L_\infty$-norm (Chebyshev distance) and distinguishes between four main variants based on two axes:

1. Symmetry:
   • Directed ($\delta_{\vec{H}}$): $\max_{p \in P} \min_{q \in Q} \|p - q\|_\infty$. Asymmetric; measures how well $P$ fits into $Q$.
   • Undirected ($\delta_{H}$): $\max(\delta_{\vec{H}}(P, Q), \delta_{\vec{H}}(Q, P))$. Symmetric; a true metric.
2. Domain of Translations:
   • Continuous ($T = \mathbb{R}^d$): Finding the optimal translation in continuous space.
   • Discrete ($T$ is a finite set of size $t$): Finding the best translation from a given finite set.

The authors apply fine-grained complexity theory to determine how the running time depends on $n$, $m$, $d$, and the specific variant, challenging the assumption that the complexity is always symmetric with respect to $n$ and $m$.

2. Methodology

The authors employ a combination of algorithmic design and conditional lower bound proofs based on standard hardness hypotheses in fine-grained complexity:

• Hardness Hypotheses:
  • $k$-Clique Hypothesis: No $O(n^{k-\epsilon})$ algorithm exists for finding a $k$-clique.
  • $k$-Hyperclique Hypothesis: No $O(n^{k-\epsilon})$ algorithm exists for finding a $k$-hyperclique in a $u$-uniform hypergraph.
  • Orthogonal Vectors Hypothesis (OVH): No $O(n^{2-\epsilon})$ algorithm exists for the Orthogonal Vectors problem.
  • 3SUM Hypothesis: No $O(n^{2-\epsilon})$ algorithm exists for 3SUM.
  • MaxConv LowerBound: A problem related to $(\min, +)$-convolution.
• Reductions: The paper utilizes reductions from these hard problems to the Hausdorff distance variants. Key techniques include:
  • Encoding Graphs into Hypercubes: Mapping vertices and edges of a graph/hypergraph to cells within a $d$-dimensional hypercube.
  • Feasible vs. Forbidden Regions: Covering "forbidden" regions (representing non-edges) with geometric shapes (boxes, orthants) to ensure that a valid translation exists if and only if a solution to the source problem (e.g., a clique) exists.
  • Prefix Covering Designs: Using specific sequences to encode vertices redundantly to achieve tight bounds in 3D.
  • Complement Trick: Transforming the existential quantifier in the discrete problem into a universal one by considering the complement of the union of boxes, enabling reductions to 3SUM.

3. Key Contributions and Results

A. Asymmetry in Complexity (Directed Case, $d \ge 3$)

The most significant finding is that the time complexity of the directed Hausdorff distance is intrinsically asymmetric with respect to $n$ and $m$, contradicting previous symmetric bounds.

• Balanced/Small $m$ ($m \le \sqrt{n}$): For $d=3$ and $m \le \sqrt{n}$, the authors prove a tight conditional lower bound of $(nm)^{d/2 - o(1)}$. This matches the best known upper bound and confirms the hardness of the balanced case.
• Unbalanced/Small $n$ ($n \ll m$):
  • Algorithm: For $d=3$ and $n = m^{o(1)}$, they present an almost-linear time algorithm with complexity $\tilde{O}(m^{1+o(1)})$. This beats the generic $(nm)^{d/2}$ bound significantly when $n$ is small.
  • Lower Bound: They prove a lower bound of $m^{\lfloor d/2 \rfloor - o(1)}$ for small $n$.
  • Implication: The complexity is not $(nm)^{d/2}$ generally; it depends heavily on the ratio of $n$ to $m$.

B. Dimensionality and Symmetry (Directed vs. Undirected)

• $d \ge 3$: The lower bounds derived for the directed case also apply to the undirected case. The authors show that the undirected problem is not significantly easier than the directed one in higher dimensions.
• $d = 1$: A sharp separation exists.
  • Undirected: Solvable in near-linear time $\tilde{O}(n+m)$ (Rote, 1991).
  • Directed: Proven to be at least as hard as MaxConv LowerBound (and $L_\infty$-Necklace Alignment). This suggests the directed 1D case likely requires quadratic time, unlike its undirected counterpart.
  • Reduction: The authors provide a reduction from the directed 1D case to the undirected 2D case (by doubling dimensions), showing that if MaxConv is hard, the undirected case is hard for $d \ge 2$.

C. Discreteness vs. Continuity

• Continuous ($d=2$): A tight lower bound of $(nm)^{1-o(1)}$ exists under OVH (Bringmann & Nusser).
• Discrete ($d \le 3$): The authors show that the discrete variant reduces to All-Ints 3SUM (a variant of 3SUM).
  • This implies that proving a tight OVH-based lower bound for the discrete case would imply a tight reduction from Orthogonal Vectors to 3SUM, a major open problem in fine-grained complexity.
  • Consequently, the discrete case for $d \le 3$ is likely easier (or at least not OVH-hard in the same way) than the continuous case, or the hardness stems from different sources (like 3SUM).

D. Summary of Bounds (Balanced Case $n=m$)

Dimension	Directed (Continuous)	Directed (Discrete)	Undirected (Continuous)
$d=1$	$\tilde{O}(n^2)$ (Hardness: MaxConv)	$\tilde{O}(n^2)$	$\tilde{O}(n)$
$d=2$	$\tilde{O}(n^2)$ (Tight: OVH)	$\tilde{O}(n^2)$ (Reduces to 3SUM)	$\tilde{O}(n^2)$ (Tight: OVH)
$d=3$	$\tilde{O}(n^3)$ (Lower: $n^{2.25}$)	$\tilde{O}(n^3)$ (Reduces to 3SUM)	$\tilde{O}(n^3)$ (Lower: $n^{2.25}$)
$d \ge 4$	$\tilde{O}((nm)^{d/2})$	$\tilde{O}((nm)^{d/2})$	$\tilde{O}((nm)^{d/2})$

(Note: For $d=3$, the lower bound is $n^{2.25}$, leaving a gap with the $n^3$ upper bound.)

4. Significance

1. Refutation of Symmetry: The paper fundamentally changes the understanding of Hausdorff distance complexity by proving that for directed distances in $d \ge 3$, the complexity is not symmetric in $n$ and $m$. This breaks the tradition of assuming $(nm)^{d/2}$ is the universal barrier.
2. Algorithmic Breakthrough: The discovery of an almost-linear algorithm for the unbalanced directed case ($n \ll m$) in 3D provides a practical improvement for scenarios where one shape is much smaller than the other.
3. Complexity Landscape: It maps the intricate relationship between dimensionality, symmetry, and discreteness. It highlights that $d=1$ is unique due to the separation between directed and undirected complexities, while $d \ge 3$ unifies them but introduces asymmetry.
4. Connections to Core Problems: The work strengthens the links between geometric pattern matching and fundamental problems like 3SUM, MaxConv, and Hyperclique, suggesting that progress in one area may unlock the others.

5. Open Questions

The authors identify several open problems:

• Closing the Gap: For $d=3$ and balanced inputs, there is a gap between the lower bound ($n^{2.25}$) and the upper bound ($n^3$).
• Cutoff Point: Determining the exact threshold where the complexity shifts from $(nm)^{d/2}$ to the faster unbalanced algorithms.
• Higher Dimensions ($d \ge 4$): Extending the tight lower bounds and the unbalanced algorithm to higher dimensions, which is currently hindered by the lack of prefix covering designs for $d \ge 4$.
• Discrete vs. Continuous: Fully resolving the hardness of the discrete case for $d > 3$ and its relationship to 3SUM.