Autor:	Jungeblut, Paul, Kleist, Linda, Miltzow, Tillmann
Rok vydání:	2021
Předmět:	Computer Science - Computational Geometry Computer Science - Computational Complexity
Druh dokumentu:	Working Paper
Popis:	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 $\forall\exists_<\mathbb{R}$. This implies that the problem is NP-, co-NP-, $\exists\mathbb{R}$- and $\forall\mathbb{R}$-hard. Comment: Preliminary version appeared at SoCG 2022
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2112.04343 Zobrazit plný text záznamu View this record from Arxiv