NP-Membership for the Boundary-Boundary Art-Gallery Problem

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. That is, for each point on the boundary, there should be a line segment connecting it to one of the guards that is contained in P. We show that this art-gallery variant is in NP, even if the polygon can have holes. In order to prove this, we develop a constraint-propagation procedure for continuous constraint satisfaction problems where each constraint involves at most 2 variables.