The Art Gallery Problem is ∃ℝ-complete

DOI10.1145/3486220OpenAlexW4205566938WikidataQ130963703 ScholiaQ130963703MaRDI QIDQ5066941FDOQ5066941

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

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

zbMATH Keywords

art gallery problemexistential theory of the reals

Mathematics Subject Classification ID

Computer science (68-XX)

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)