The Complexity of the Hausdorff Distance
Paul Jungeblut, Linda Kleist, Tillmann Miltzow · Discrete & Computational Geometry · 2023
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 $${ \forall \exists _{<}\mathbb {R}} $$ ∀ ∃ < R . This implies that the problem is -, -, $$\exists \mathbb {R} $$ ∃ R -, and $$\forall \mathbb {R} $$ ∀ R -hard.