The Complexity of the Hausdorff Distance

Paul Jungeblut; Linda Kleist; Till Miltzow

doi:10.4230/LIPIcs.SoCG.2022.48

The Complexity of the Hausdorff Distance

Paul Jungeblut
, Linda Kleist
, Till Miltzow

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 ∀∃_

Original language	English
Title of host publication	38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany
Editors	Xavier Goaoc, Michael Kerber
Publisher	Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
Pages	48:1-48:17
Volume	224
ISBN (Electronic)	9783959772273
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2022.48
Publication status	Published - 1 Jun 2022

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	224
ISSN (Print)	1868-8969

Bibliographical 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:
© Paul Jungeblut, Linda Kleist, and Tillmann Miltzow; licensed under Creative Commons License CC-BY 4.0

Keywords

Hausdorff Distance
Semi-Algebraic Set
Existential Theory of the Reals
Universal Existential Theory of the Reals
Complexity Theory

Access to Document

10.4230/LIPIcs.SoCG.2022.48Licence: CC BY

LIPIcs-SoCG-2022-48Final published version, 1.37 MBLicence: CC BY

Cite this

Jungeblut, P., Kleist, L., & Miltzow, T. (2022). The Complexity of the Hausdorff Distance. In X. Goaoc, & M. Kerber (Eds.), 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany (Vol. 224, pp. 48:1-48:17). Article 48 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 224). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.SoCG.2022.48

Jungeblut, Paul ; Kleist, Linda ; Miltzow, Till. / The Complexity of the Hausdorff Distance. 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany. editor / Xavier Goaoc ; Michael Kerber. Vol. 224 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, 2022. pp. 48:1-48:17 (Leibniz International Proceedings in Informatics, LIPIcs).

@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",

}

Jungeblut, P, Kleist, L & Miltzow, T 2022, The Complexity of the Hausdorff Distance. in X Goaoc & M Kerber (eds), 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany. vol. 224, 48, Leibniz International Proceedings in Informatics, LIPIcs, vol. 224, Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, pp. 48:1-48:17. https://doi.org/10.4230/LIPIcs.SoCG.2022.48

The Complexity of the Hausdorff Distance. / Jungeblut, Paul; Kleist, Linda; Miltzow, Till.
38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany. ed. / Xavier Goaoc; Michael Kerber. Vol. 224 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, 2022. p. 48:1-48:17 48 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 224).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The Complexity of the Hausdorff Distance

AU - Jungeblut, Paul

AU - Kleist, Linda

AU - Miltzow, Till

N1 - 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: © Paul Jungeblut, Linda Kleist, and Tillmann Miltzow; licensed under Creative Commons License CC-BY 4.0

PY - 2022/6/1

Y1 - 2022/6/1

N2 - 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 ∀∃_

AB - 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 ∀∃_

KW - Hausdorff Distance

KW - Semi-Algebraic Set

KW - Existential Theory of the Reals

KW - Universal Existential Theory of the Reals

KW - Complexity Theory

UR - https://www.scopus.com/pages/publications/85134315839

U2 - 10.4230/LIPIcs.SoCG.2022.48

DO - 10.4230/LIPIcs.SoCG.2022.48

M3 - Conference contribution

VL - 224

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 48:1-48:17

BT - 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany

A2 - Goaoc, Xavier

A2 - Kerber, Michael

PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH

ER -

Jungeblut P, Kleist L, Miltzow T. The Complexity of the Hausdorff Distance. In Goaoc X, Kerber M, editors, 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany. Vol. 224. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. 2022. p. 48:1-48:17. 48. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.SoCG.2022.48

The Complexity of the Hausdorff Distance

Abstract

Publication series

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this