@inproceedings{57123b8c095d4e32b69fe677f867eed9,
title = "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 ∀∃_",
keywords = "Hausdorff Distance, Semi-Algebraic Set, Existential Theory of the Reals, Universal Existential Theory of the Reals, Complexity Theory",
author = "Paul Jungeblut and Linda Kleist and Till Miltzow",
note = "Funding Information: Funding Linda Kleist: Partially supported by a postdoc fellowship of the German Academic Exchange Service (DAAD). Tillmann Miltzow: Generously supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250. Publisher Copyright: {\textcopyright} Paul Jungeblut, Linda Kleist, and Tillmann Miltzow; licensed under Creative Commons License CC-BY 4.0",
year = "2022",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SoCG.2022.48",
language = "English",
volume = "224",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik GmbH",
pages = "48:1--48:17",
editor = "Xavier Goaoc and Michael Kerber",
booktitle = "38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany",
}