2026-07-23T17:33:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17874 2024-03-06T11:00:35Z ddc:004 open_access

Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee’s Measure Problem Chan, Timothy M. Hausdorff distance geometric optimization Klee’s measure problem fine-grained complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.24 urn:nbn:de:0030-drops-178741 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.24 eng https://creativecommons.org/licenses/by/4.0/legalcode