The complexity of the Hausdorff distance

DOI10.1007/s00454-023-00562-5arXiv2112.04343OpenAlexW4387097174MaRDI QIDQ6145675

Linda Kleist, Paul Jungeblut, Tillmann Miltzow

Publication date: 9 January 2024

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2112.04343

zbMATH Keywords

semi-algebraic setHausdorff distancecomplexity theoryexistential theory of the realsuniversal existential theory of the reals

Mathematics Subject Classification ID

Theory of computing (68Qxx) Graph theory (05Cxx) Real algebraic and real-analytic geometry (14Pxx)

Cites Work

• Recognition and complexity of point visibility graphs
• Fixed points, Nash equilibria, and the existential theory of the reals
• A linear time algorithm for the Hausdorff distance between convex polygons
• Bounding the radii of balls meeting every connected component of semi-algebraic sets
• Realizability of graphs in three dimensions
• Exotic quantifiers, complexity classes, and complete problems
• Estimates of real roots of a system of algebraic equations
• Solving systems of polynomial inequalities in subexponential time
• Real quantifier elimination is doubly exponential
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• \(\forall\exists\mathbb {R}\)-completeness and area-universality
• Approximate matching of polygonal shapes
• Integer realizations of disk and segment graphs
• Computational complexity of multi-player evolutionarily stable strategies
• Efficient visual recognition using the Hausdorff distance
• Realizability of Graphs and Linkages
• Who Needs Crossings? Hardness of Plane Graph Rigidity
• Complexity of Some Geometric and Topological Problems
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Realization spaces of 4-polytopes are universal
• The Complexity of Drawing a Graph in a Polygonal Region
• The Art Gallery Problem is ∃ℝ-complete
• Algorithms in real algebraic geometry
• Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item