The Art Gallery Problem is ∃ℝ-complete

DOI10.1145/3486220MaRDI QIDQ5066941zbMATH OpenOpenAlexWikidataFDO

Authors Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow

Publication date 31 March 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3486220

zbMATH Keywords

art gallery problemexistential theory of the reals

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• The art gallery problem is \(\exists \mathbb{R}\)-complete
• Computational complexity of art gallery problems
• Parameterized Hardness of Art Gallery Problems
• Parameterized hardness of art gallery problems
• Facets for art gallery problems

Cited in

(14)

• Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
• On classifying continuous constraint satisfaction problems
• The complexity of the Hausdorff distance
• On the complexity of recognizing nerves of convex sets
• Observation routes and external watchman routes
• RAC-Drawability is ∃ℝ-complete and Related Results
• Observation routes and external watchman routes
• Topological universality of the art gallery problem
• The complexity of drawing a graph in a polygonal region
• The dispersive art gallery problem
• Beyond the Existential Theory of the Reals
• The Complexity of Angular Resolution
• Minimizing visible edges in polyhedra
• Guarding polyominoes under \(k\)-hop visibility

This page was built for publication: The Art Gallery Problem is ∃ℝ-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066941)