The art gallery problem is ∃ ℝ-complete
From MaRDI portal
Publication:5230277
DOI10.1145/3188745.3188868zbMath1427.68324arXiv1704.06969OpenAlexW2612212426MaRDI QIDQ5230277
Tillmann Miltzow, Mikkel Abrahamsen, Anna Adamaszek
Publication date: 22 August 2019
Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.06969
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ Smoothing the Gap Between NP and ER ⋮ Art gallery problem with rook and queen vision ⋮ Spaces of geodesic triangulations of surfaces ⋮ Optimally guarding 2-reflex orthogonal polyhedra by reflex edge guards ⋮ The visible-volume function of a set of cameras is continuous, piecewise rational, locally Lipschitz, and semi-algebraic in all dimensions ⋮ Reflective guarding a gallery ⋮ The Complexity of Positive Semidefinite Matrix Factorization ⋮ IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING? ⋮ Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality ⋮ The parameterized complexity of guarding almost convex polygons ⋮ Topological art in simple galleries ⋮ Finding minimum witness sets in orthogonal polygons ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ The complexity of drawing a graph in a polygonal region ⋮ Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals ⋮ Drawing graphs as spanners ⋮ Drawing Clustered Planar Graphs on Disk Arrangements ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem ⋮ Computational complexity of multi-player evolutionarily stable strategies ⋮ A constant-factor approximation algorithm for vertex guarding a WV-polygon
