The Complexity of the Hausdorff Distance

Paul Jungeblut; Linda Kleist; Tillmann Miltzow

doi:10.1007/s00454-023-00562-5

The Complexity of the Hausdorff Distance

Paul Jungeblut^*, Linda Kleist^*, Tillmann Miltzow^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › 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 ∀ ∃ _<R . This implies that the problem is NP-, co- NP-, ∃ R -, and ∀ R -hard.

Original language	English
Pages (from-to)	177-213
Number of pages	37
Journal	Discrete and Computational Geometry
Volume	71
Issue number	1
DOIs	https://doi.org/10.1007/s00454-023-00562-5
Publication status	Published - Jan 2024

Bibliographical note

Publisher Copyright:
© 2023, The Author(s).

Keywords

Complexity theory
Existential theory of the reals
Hausdorff distance
Semi-algebraic set
Universal existential theory of the reals

Access to Document

10.1007/s00454-023-00562-5Licence: CC BY

s00454-023-00562-5Final published version, 984 KBLicence: CC BY

Cite this

@article{575417cfed25488399f2ac6226ab4dfd,

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 ∀ ∃ <R . This implies that the problem is NP-, co- NP-, ∃ R -, and ∀ R -hard.",

keywords = "Complexity theory, Existential theory of the reals, Hausdorff distance, Semi-algebraic set, Universal existential theory of the reals",

author = "Paul Jungeblut and Linda Kleist and Tillmann Miltzow",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s).",

year = "2024",

month = jan,

doi = "10.1007/s00454-023-00562-5",

language = "English",

volume = "71",

pages = "177--213",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - The Complexity of the Hausdorff Distance

AU - Jungeblut, Paul

AU - Kleist, Linda

AU - Miltzow, Tillmann

PY - 2024/1

Y1 - 2024/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 ∀ ∃ <R . This implies that the problem is NP-, co- NP-, ∃ R -, and ∀ R -hard.

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 ∀ ∃ <R . This implies that the problem is NP-, co- NP-, ∃ R -, and ∀ R -hard.

KW - Complexity theory

KW - Existential theory of the reals

KW - Hausdorff distance

KW - Semi-algebraic set

KW - Universal existential theory of the reals

UR - http://www.scopus.com/inward/record.url?scp=85172660266&partnerID=8YFLogxK

U2 - 10.1007/s00454-023-00562-5

DO - 10.1007/s00454-023-00562-5

M3 - Article

AN - SCOPUS:85172660266

SN - 0179-5376

VL - 71

SP - 177

EP - 213

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

The Complexity of the Hausdorff Distance

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this