KIT | KIT-Bibliothek | Impressum | Datenschutz

The Complexity of the Hausdorff Distance

Jungeblut, Paul ORCID iD icon 1; Kleist, L. ; Miltzow, T.
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

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.


Verlagsausgabe §
DOI: 10.5445/IR/1000149134
Veröffentlicht am 28.07.2022
Originalveröffentlichung
DOI: 10.4230/LIPIcs.SoCG.2022.48
Scopus
Zitationen: 4
Cover der Publikation
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
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page