The Complexity of the Hausdorff 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 ∀∃_<ℝ. This implies that the problem is NP-, co-NP-, ∃ℝ- and ∀ℝ-hard.
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Proceedingsbeitrag |
| Publikationsjahr | 2022 |
| Sprache | Englisch |
| Identifikator | ISBN: 978-3-9597722-7-3 ISSN: 1868-8969 KITopen-ID: 1000149134 |
| Erschienen in | 38th International Symposium on Computational Geometry (SoCG 2022). Ed.: X. Goaoc |
| Veranstaltung | 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Deutschland, 07.06.2022 – 10.06.2022 |
| Verlag | Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI) |
| Seiten | Art.-Nr.: 48 |
| Serie | Leibniz International Proceedings in Informatics (LIPIcs) ; 224 |
| Schlagwörter | Hausdorff Distance, Semi-Algebraic Set, Existential Theory of the Reals, Universal Existential Theory of the Reals, Complexity Theory |
| Nachgewiesen in | Scopus |