NP-membership for the boundary-boundary art-gallery problem

Jack Stade · 2025

Read NP-membership for the boundary-boundary art-gallery problem by Jack Stade (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01562.txt.

Introduction

Jack Stade settles a complexity question about the art gallery problem, the classic puzzle of placing the fewest guards so every wall of a polygonal gallery is watched. In the boundary-boundary variant, guards stand on the boundary and only the boundary must be seen, but guards' sight lines must stay inside the polygon, holes included.

Neighbors of this variant were known to be NP-complete or complete for a larger real-number class, leaving boundary-boundary stranded somewhere between NP and that class. Stade shows it is in NP. The proof builds a constraint-propagation procedure for continuous constraint satisfaction problems. In these problems each constraint involves at most two variables. An example is needed first, to show the solution cannot simply be reduced to a discrete set-cover instance.

Catalog record

CREATORJack Stade
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-01562

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

NP-membership for the boundary-boundary art-gallery problem Jack Stade Abstract The boundary-boundary art-gallery problem asks, given a polygon P P representing an art-gallery, for a minimal set of guards that can see the entire boundary of P 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 ∃ ℝ \exists\mathbb{R} -complete [Abrahamsen, Adamaszek, and Miltzow, JACM 2021][Stade, SoCG 2025]. However, the boundary-boundary variant was only known to lie somewhere between NP and ∃ ℝ \exists\mathbb{R} . 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. 1 Introduction Given a plane polygon P , two points x and y in P are said to be visible to each other if the line segment between x and y is contained P . The art-gallery problem [ 22 ] is a decision problem that asks, given a polygon P (called the art-gallery), whether there are n points in P (called the guards) such that every point in P is visible to at least one of the guards. For X,Y\in\{\text{Vertex, Boundary, Point}\} , the X-Y art-gallery problem [ 5 ] is a variants of the art-gallery problem where the guards are restricted to lie in X, but only need to see Y. The original variant (as described above) is called the point-point variant under this system. The variant where the guards only need to see the boundary of the polygon is called the point-boundary variant. All of these variants are at least NP-hard [ 17 , 16 ] , but it isn’t clear that they are necessarily contained in NP. The coordinates of the guards can be arbitrary real numbers, and some instances require guards to be placed at irrational coordinates in order to be guarded optimally, even when the vertices of P are given as integers (see [ 1 ] ). The problem ETR (short for Existential Theory of the Reals) asks whether a statement of form: \exists x_{1},\dots,x_{n}\in\mathbb{R}:\Phi(x_{1},\dots,x_{n}) is true, where \Phi is a boolean formula involving the signs of integer-coefficient polynomials in the variables x_{1},\dots,x_{n} . The complexity class \exists\mathbb{R} consists of problems that can be polynomial-time reduced to ETR. It is straightforward to see that \text{NP}\subseteq\exists\mathbb{R} . In 1988, Canny [ 10 ] established that \exists\mathbb{R}\subseteq\text{PSPACE} . It is unknown whether either inclusion is strict. In 2018, Abrahamsen, Adamaszek and Miltzow [ 2 ] showed that the point-point and boundary-point art-gallery variants are \exists\mathbb{R} -complete, meaning in particular that they are not contained in NP unless NP =\exists\mathbb{R} . Stade [ 28 ] later proved the point-boundary variant is also \exists\mathbb{R} -complete. In contrast, all the vertex-Y and X-vertex variants are easily seen to be in NP. We show that the boundary-boundary variant is in NP, completing the classification of the complexities of X-Y art-gallery variants (at least up to \text{NP}\stackrel{{\scriptstyle?}}{{=}}\exists\mathbb{R} ). This is summarized in Table 1 . Variant Complexity Vertex-Y NP [ 17 ] X-Vertex NP [ 17 ] Point-Point \exists\mathbb{R} [ 2 ] Boundary-Point \exists\mathbb{R} [ 2 ] Point-Boundary \mathbf{\exists\mathbb{R}} [ 28 ] Boundary-Boundary NP[ this paper ] Table 1: Complexity of X-Y art-gallery variants 1.1 Background and related work Biniaz, Maheshwari, Merrild, Mitchell, Odak, Polishchuk, Robson, Rysgaard, Schou, Shermer, Spalding-Jamieson, Svenning, and Zheng [ 8 ] recently gave a polynomial time algorithm for the contiguous art gallery problem , a variant of the point-boundary art-gallery where each guard can be responsible only for a connected section of the polygon boundary. In addition to art-galleries, many other important problems are known to be \exists\mathbb{R} -complete, notable examples including packing [ 4 ] , drawing graphs with fixed edge lengths [ 23 ] , realizeability of line arrangements [ 21 , 27 ] , and training neural networks [ 3 , 7 ] . A recent survey by Cardinal, Miltzow and Schaefer [ 24 ] lists roughly 150 \exists\mathbb{R} -complete problems. A constraint satisfaction problem (CSP) is a decision problem that asks whether there is an assignment of some variables that satisfies a set of constraints. A 2CSP is a CSP where each constraint involves at most 2 variables. A continuous constraint satisfaction problem (CCSP) is a constraint satisfaction problem where the variables take values over a continuous domain, typically \mathbb{R} or a subset thereof. The constraints are typically represented by equalities and inequalities involving polynomials in the variables. A 2CCSP is a CCSP where each constraint involves at most 2 variables. Discrete CSPs are typically in NP and are frequently NP-complete. Similarly, CCSPs are typically in \exists\mathbb{R} and are frequently \exists\mathbb{R} -complete. Miltzow and Schmiermann [ 19 ] showed that CCSPs typically become \exists\mathbb{R} -hard if constraints of form x+y=z can occur along with some nonlinear constraints. They conjecture that it is necessary to have a constraints that depends on 3 or more variables in order for a CCSP to be \exists\mathbb{R} -hard, as current techniques seem to be unable to show \exists\mathbb{R} -hardness for any 2CCSPs. It has been know since at least 1967 [ 15 ] that boolean 2CSPs can be decided in polynomial time. On the other hand, ternary 2CSPs are already NP-hard [ 6 ] . In 2000, Beckert, Hahnle and Manya [ 6 ] gave a polynomial-time algorithm for solving 2CSPS where the variables lie in a lattice and the constraints are disjunctions of terms of form x\geq c or x\leq c . Charatonik and Wrona [ 11 ] later gave a faster algorithm for these instances. One very important example of a CCSP is linear programming. In 1983, Megiddo [ 18 ] gave a strongly polynomial time algorithm for determining feasibility of a linear programming instance where each constraint involves at most 2 variables. In 2023, Dadush, Koh, Natura, Olver, and Végh [ 12 ] gave a strongly polynomial time algorithm for determining optimality for these instances. The best known algorithms for general linear programming run in only weakly polynomial time. A common technique for solving CSPs is constraint propagation : given an instance \Gamma , we can derive new constraints from the existing ones. A method for producing new constraints giving existing ones is called an inference rule . If we can derive the unsatisfiable clause \emptyset from the original instance using some set of inference rules, then we conclude that the instance is unsatisfiable. A derivation of \emptyset is called a refutation of the instance. A set of inference rules for a

Read the complete text