The art gallery problem is ∃ ℝ-complete

TY - GEN

T1 - The art gallery problem is ∃ ℝ-complete

AU - Abrahamsen, Mikkel

AU - Adamaszek, Anna

AU - Miltzow, Tillmann

PY - 2018/6/20

Y1 - 2018/6/20

N2 - We prove that the art gallery problem is equivalent under polynomial time reductions to deciding whether a system of polynomial equations over the real numbers has a solution. The art gallery problem is a classic problem in computational geometry, introduced in 1973 by Victor Klee. Given a simple polygon P and an integer k, the goal is to decide if there exists a set G of k guards within P such that every point p ∈ P is seen by at least one guard ∈ G. Each guard corresponds to a point in the polygon P, and we say that a guard sees a point p if the line segment p is contained in P. The art gallery problem has stimulated extensive research in geometry and in algorithms. However, the complexity status of the art gallery problem has not been resolved. It has long been known that the problem is NP-hard, but no one has been able to show that it lies in NP. Recently, the computational geometry community became more aware of the complexity class ∃R, which has been studied earlier by other communities. The class ∃R consists of problems that can be reduced in polynomial time to the problem of deciding whether a system of polynomial equations with integer coefficients and any number of real variables has a solution. It can be easily seen that NP ⊆ ∃R. We prove that the art gallery problem is ∃R-complete, implying that (1) any system of polynomial equations over the real numbers can be encoded as an instance of the art gallery problem, and (2) the art gallery problem is not in the complexity class NP unless NP = ∃R. As a corollary of our construction, we prove that for any real algebraic number, there is an instance of the art gallery problem where one of the coordinates of the guards equals in any guard set of minimum cardinality. That rules out many natural geometric approaches to the problem, as it shows that any approach based on constructing a finite set of candidate points for placing guards has to include points with coordinates being roots of polynomials with arbitrary degree. As an illustration of our techniques, we show that for every compact semi-algebraic set S ⊆ [0, 1]2, there exists a polygon with corners at rational coordinates such that for every p ∈ [0, 1]2, there is a set of guards of minimum cardinality containing p if and only if p ∈ S. In the ∃R-hardness proof for the art gallery problem, we introduce a new ∃R-complete problem ETR-INV. We believe that this problem is of independent interest, as it can be used to obtain Rhardness proofs for other problems. In particular, ETR-INV has been used very recently to prove R-hardness of other geometric problems.

AB - We prove that the art gallery problem is equivalent under polynomial time reductions to deciding whether a system of polynomial equations over the real numbers has a solution. The art gallery problem is a classic problem in computational geometry, introduced in 1973 by Victor Klee. Given a simple polygon P and an integer k, the goal is to decide if there exists a set G of k guards within P such that every point p ∈ P is seen by at least one guard ∈ G. Each guard corresponds to a point in the polygon P, and we say that a guard sees a point p if the line segment p is contained in P. The art gallery problem has stimulated extensive research in geometry and in algorithms. However, the complexity status of the art gallery problem has not been resolved. It has long been known that the problem is NP-hard, but no one has been able to show that it lies in NP. Recently, the computational geometry community became more aware of the complexity class ∃R, which has been studied earlier by other communities. The class ∃R consists of problems that can be reduced in polynomial time to the problem of deciding whether a system of polynomial equations with integer coefficients and any number of real variables has a solution. It can be easily seen that NP ⊆ ∃R. We prove that the art gallery problem is ∃R-complete, implying that (1) any system of polynomial equations over the real numbers can be encoded as an instance of the art gallery problem, and (2) the art gallery problem is not in the complexity class NP unless NP = ∃R. As a corollary of our construction, we prove that for any real algebraic number, there is an instance of the art gallery problem where one of the coordinates of the guards equals in any guard set of minimum cardinality. That rules out many natural geometric approaches to the problem, as it shows that any approach based on constructing a finite set of candidate points for placing guards has to include points with coordinates being roots of polynomials with arbitrary degree. As an illustration of our techniques, we show that for every compact semi-algebraic set S ⊆ [0, 1]2, there exists a polygon with corners at rational coordinates such that for every p ∈ [0, 1]2, there is a set of guards of minimum cardinality containing p if and only if p ∈ S. In the ∃R-hardness proof for the art gallery problem, we introduce a new ∃R-complete problem ETR-INV. We believe that this problem is of independent interest, as it can be used to obtain Rhardness proofs for other problems. In particular, ETR-INV has been used very recently to prove R-hardness of other geometric problems.

U2 - 10.1145/3188745.3188868

DO - 10.1145/3188745.3188868

M3 - Article in proceedings

SP - 65

EP - 73

BT - STOC 2018 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018

Y2 - 25 June 2018 through 29 June 2018

ER -