Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem

2023/03/16 by Chan, Timothy M.
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2303.09122

Abstract

We present a (combinatorial) algorithm with running time close to O(n^d) for computing the minimum directed L_∞ Hausdorff distance between two sets of n points under translations in any constant dimension d. This substantially improves the best previous time bound near O(n^5d/4) by Chew, Dor, Efrat, and Kedem from more than twenty years ago. Our solution is obtained by a new generalization of Chan's algorithm [FOCS'13] for Klee's measure problem. To complement this algorithmic result, we also prove a nearly matching conditional lower bound close to Ω(n^d) for combinatorial algorithms, under the Combinatorial k-Clique Hypothesis.

Related

• Approximating the Directed Hausdorff Distance
• Approximating the Directed Hausdorff Distance
• Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation
• Partial-Matching and Hausdorff RMS Distance Under Translation: Combinatorics and Algorithms
• Computational Aspects of the Hausdorff Distance in Unbounded Dimension