Discrete & Computational Geometry · 2023 · 13 citations · 23 references
ComputingComputer ScienceMathematicsAlgorithmsSet TheoryTheory Of ComputationAlgorithmic ComplexityComplexity TheoryComputational ComplexityMetric GeometryCompleteness ResultsComplexity-theoretic HardnessHausdorff Distance
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.
23
James Renegar · Journal of Symbolic Computation · 1992 · 622 citations
Some algebraic and geometric computations in PSPACE
John Canny · 1988 · 581 citations · Full text