The Complexity of the Hausdorff Distance
Copyright policy )The Complexity of the Hausdorff Distance
AbstractWe 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.
- Technische Universität Braunschweig Germany
- Utrecht University Netherlands
- Karlsruhe Institute of Technology Germany
- Leibniz Association Germany
- Schloss Dagstuhl – Leibniz Center for Informatics Germany
ddc:004, Computational Geometry (cs.CG), FOS: Computer and information sciences, Existential Theory of the Reals, Hausdorff distance, Complexity theory, Universal Existential Theory of the Reals, DATA processing & computer science, Computational Complexity (cs.CC), Hausdorff Distance, 004, Computer Science - Computational Complexity, Existential theory of the reals, Semi-algebraic set, Semi-Algebraic Set, Computer Science - Computational Geometry, Universal existential theory of the reals, info:eu-repo/classification/ddc/004, Complexity Theory, ddc: ddc:004
ddc:004, Computational Geometry (cs.CG), FOS: Computer and information sciences, Existential Theory of the Reals, Hausdorff distance, Complexity theory, Universal Existential Theory of the Reals, DATA processing & computer science, Computational Complexity (cs.CC), Hausdorff Distance, 004, Computer Science - Computational Complexity, Existential theory of the reals, Semi-algebraic set, Semi-Algebraic Set, Computer Science - Computational Geometry, Universal existential theory of the reals, info:eu-repo/classification/ddc/004, Complexity Theory, ddc: ddc:004
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).7 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!