The Complexity of the Hausdorff Distance
Publication date
2024-01
Authors
Jungeblut, Paul
Kleist, Linda
Miltzow, Tillmann
Editors
Advisors
Supervisors
Document Type
Article
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 ∀ ∃ <R . This implies that the problem is NP-, co- NP-, ∃ R -, and ∀ R -hard.
Keywords
Complexity theory, Existential theory of the reals, Hausdorff distance, Semi-algebraic set, Universal existential theory of the reals, Theoretical Computer Science, Geometry and Topology, Discrete Mathematics and Combinatorics, Computational Theory and Mathematics
Citation
Jungeblut, P, Kleist, L & Miltzow, T 2024, 'The Complexity of the Hausdorff Distance', Discrete and Computational Geometry, vol. 71, no. 1, pp. 177-213. https://doi.org/10.1007/s00454-023-00562-5