The Complexity of the Hausdorff Distance
Publication date
2022-06-01
Authors
Jungeblut, Paul
Kleist, Linda
Miltzow, Tillmann
Editors
Goaoc, Xavier
Kerber, Michael
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
cc_by
Abstract
We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algebraic sets is bounded by a given threshold is complete for the complexity class ∀∃_
Keywords
Hausdorff Distance, Semi-Algebraic Set, Existential Theory of the Reals, Universal Existential Theory of the Reals, Complexity Theory
Citation
Jungeblut, P, Kleist, L & Miltzow, T 2022, The Complexity of the Hausdorff Distance. in X Goaoc & M Kerber (eds), 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany. vol. 224, 48, Leibniz International Proceedings in Informatics, LIPIcs, vol. 224, Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, pp. 48:1-48:17. https://doi.org/10.4230/LIPIcs.SoCG.2022.48