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

Timothy M. Chan

doi:10.4230/LIPIcs.SoCG.2023.24

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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⁵d/⁴) 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.

Original language	English (US)
Title of host publication	39th International Symposium on Computational Geometry, SoCG 2023
Editors	Erin W. Chambers, Joachim Gudmundsson
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959772730
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2023.24
State	Published - Jun 1 2023
Externally published	Yes
Event	39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, United States Duration: Jun 12 2023 → Jun 15 2023

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	258
ISSN (Print)	1868-8969

Conference

Conference	39th International Symposium on Computational Geometry, SoCG 2023
Country/Territory	United States
City	Dallas
Period	6/12/23 → 6/15/23

Keywords

Hausdorff distance
Klee's measure problem
fine-grained complexity
geometric optimization

ASJC Scopus subject areas

Software

Online availability

10.4230/LIPIcs.SoCG.2023.24

Library availability

Discover UIUC Full Text

Cite this

Chan, T. M. (2023). Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem. In E. W. Chambers, & J. Gudmundsson (Eds.), 39th International Symposium on Computational Geometry, SoCG 2023 Article 24 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 258). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2023.24

Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem. / Chan, Timothy M.
39th International Symposium on Computational Geometry, SoCG 2023. ed. / Erin W. Chambers; Joachim Gudmundsson. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 24 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 258).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chan, TM 2023, Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem. in EW Chambers & J Gudmundsson (eds), 39th International Symposium on Computational Geometry, SoCG 2023., 24, Leibniz International Proceedings in Informatics, LIPIcs, vol. 258, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 39th International Symposium on Computational Geometry, SoCG 2023, Dallas, United States, 6/12/23. https://doi.org/10.4230/LIPIcs.SoCG.2023.24

Chan TM. Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem. In Chambers EW, Gudmundsson J, editors, 39th International Symposium on Computational Geometry, SoCG 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 24. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.SoCG.2023.24

Chan, Timothy M. / Minimum L_∞ Hausdorff Distance of Point Sets Under Translation : Generalizing Klee's Measure Problem. 39th International Symposium on Computational Geometry, SoCG 2023. editor / Erin W. Chambers ; Joachim Gudmundsson. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{7c1e33e517fe437fae55bd61b806c82f,

title = "Minimum L∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem",

abstract = "We present a (combinatorial) algorithm with running time close to O(nd) 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(n5d/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 Ω(nd) for combinatorial algorithms, under the Combinatorial k-Clique Hypothesis.",

keywords = "Hausdorff distance, Klee's measure problem, fine-grained complexity, geometric optimization",

author = "Chan, {Timothy M.}",

note = "Work supported in part by NSF Grant CCF-2224271.; 39th International Symposium on Computational Geometry, SoCG 2023 ; Conference date: 12-06-2023 Through 15-06-2023",

year = "2023",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2023.24",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Chambers, {Erin W.} and Joachim Gudmundsson",

booktitle = "39th International Symposium on Computational Geometry, SoCG 2023",

}

TY - GEN

T1 - Minimum L∞ Hausdorff Distance of Point Sets Under Translation

T2 - 39th International Symposium on Computational Geometry, SoCG 2023

AU - Chan, Timothy M.

N1 - Work supported in part by NSF Grant CCF-2224271.

PY - 2023/6/1

Y1 - 2023/6/1

N2 - We present a (combinatorial) algorithm with running time close to O(nd) 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(n5d/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 Ω(nd) for combinatorial algorithms, under the Combinatorial k-Clique Hypothesis.

AB - We present a (combinatorial) algorithm with running time close to O(nd) 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(n5d/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 Ω(nd) for combinatorial algorithms, under the Combinatorial k-Clique Hypothesis.

KW - Hausdorff distance

KW - Klee's measure problem

KW - fine-grained complexity

KW - geometric optimization

UR - http://www.scopus.com/inward/record.url?scp=85163420008&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85163420008&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2023.24

DO - 10.4230/LIPIcs.SoCG.2023.24

M3 - Conference contribution

AN - SCOPUS:85163420008

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 39th International Symposium on Computational Geometry, SoCG 2023

A2 - Chambers, Erin W.

A2 - Gudmundsson, Joachim

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 12 June 2023 through 15 June 2023

ER -