The Complexity of the Hausdorff Distance

Speaker: Paul Jungeblut
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.

Paul won the best student presentation award with his this presentation at EuroCG 2022.