The Complexity of the Hausdorff Distance
Paul Jungeblut, Linda Kleist, Tillmann Miltzow
Abstract
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}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>∀</mml:mo> <mml:msub> <mml:mo>∃</mml:mo> <mml:mo><</mml:mo> </mml:msub> <mml:mi>R</mml:mi> </mml:mrow> </mml:math> . This implies that the problem is -, -, $$\exists \mathbb {R} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>∃</mml:mo> <mml:mi>R</mml:mi> </mml:mrow> </mml:math> -, and $$\forall \mathbb {R} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>∀</mml:mo> <mml:mi>R</mml:mi> </mml:mrow> </mml:math> -hard.