2025/11/03 by Stade, Jack
#68W40 #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #I.1.2
paper · doi:10.48550/arxiv.2511.01562
The boundary-boundary art-gallery problem asks, given a polygon P representing an art-gallery, for a minimal set of guards that can see the entire boundary of P (the wall of the art gallery), where the guards must be placed on the boundary. We show that this art-gallery variant is in NP. In order to prove this, we develop a constraint-propagation procedure for continuous constraint satisfaction problems where each constraint involves at most 2 variables. The X-Y variant of the art-gallery problem is the one where the guards must lie in X and need to see all of Y. Each of X and Y can be either the vertices of the polygon, the boundary of the polygon, or the entire polygon, giving 9 different variants. Previously, it was known that X-vertex and vertex-Y variants are all NP-complete and that the point-point, point-boundary, and boundary-point variants are ∃ ℝ-complete [Abrahamsen, Adamaszek, and Miltzow, JACM 2021][Stade, SoCG 2025]. However, the boundary-boundary variant was only known to lie somewhere between NP and ∃ ℝ. The X-vertex and vertex-Y variants can be straightforwardly reduced to discrete set-cover instances. In contrast, we give example to show that a solution to an instance of the boundary-boundary art-gallery problem sometimes requires placing guards at irrational coordinates, so it unlikely that the problem can be easily discretized.