The Complexity of the Hausdorff Distance
Not on the map. Why?
Abstract (arXiv)
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 forallexists_<ℝ. This implies that the problem is NP-, co-NP-, existsℝ- and forallℝ-hard.
Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Dec 2021.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2022: 1; 2023: 2; 2024: 0; 2025: 0; 2026: 2.
5 papers.
- 2023Neural Latent Geometry Search: Product Manifold Inference via Gromov-Hausdorff-Informed Bayesian Optimizationcited by 18
- 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
- 2023Gromov-Hausdorff Distances for Comparing Product Manifolds of Model Spacescited by 0
- 2026Feasibility-aware Imitation Learning from Observation with Multimodal Feedbackcited by 0
- 2026Learning efficient representations of complex constraints for scalable optimizationcited by 0
- 2026Learning efficient representations of complex constraints for scalable optimization9 Mar 2026
- 2026Feasibility-aware Imitation Learning from Observation with Multimodal Feedback17 Feb 2026
- 2023Gromov-Hausdorff Distances for Comparing Product Manifolds of Model Spaces9 Sep 2023
- 2023Neural Latent Geometry Search: Product Manifold Inference via Gromov-Hausdorff-Informed Bayesian Optimization9 Sep 2023
- 2022Training Fully Connected Neural Networks is existsℝ-Complete4 Apr 2022