# The Complexity of the Hausdorff Distance

arXiv: https://arxiv.org/abs/2112.04343 · HTML: https://mlsanity.com/paper/2112.04343/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2021.

## Built on by (most cited first, 5 of 5)

- [Neural Latent Geometry Search: Product Manifold Inference via Gromov-Hausdorff-Informed Bayesian Optimization](https://mlsanity.com/paper/2309.04810/) (2023)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Gromov-Hausdorff Distances for Comparing Product Manifolds of Model Spaces](https://mlsanity.com/paper/2309.05678/) (2023)
- [Feasibility-aware Imitation Learning from Observation with Multimodal Feedback](https://mlsanity.com/paper/2602.15351/) (2026)
- [Learning efficient representations of complex constraints for scalable optimization](https://mlsanity.com/paper/2603.08283/) (2026)

## 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.