The Art Gallery Problem is ∃ℝ-complete

DOI10.1145/3486220OpenAlexW4205566938MaRDI QIDQ5066941

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)

Related Items

The Complexity of Drawing a Graph in a Polygonal Region ⋮ The Complexity of Angular Resolution ⋮ Minimizing visible edges in polyhedra ⋮ The dispersive art gallery problem ⋮ The complexity of the Hausdorff distance ⋮ Observation routes and external watchman routes ⋮ RAC-Drawability is ∃ℝ-complete and Related Results ⋮ Unnamed Item