The Art Gallery Problem is $\exists \mathbb{R}$-complete

Speaker(s)

Till Miltzow

Affiliation

Universit ́e libre de Bruxelles

Date

May 11, 2017, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

The \emph{art gallery problem} is a classical problem in computational
geometry, introduced in 1973 by Viktor Klee. Given a simple polygon
\poly and an integer $k$, the goal is to decide if there exists a set
$G$ of $k$ \emph{guards} within \poly such that every point $p\in
\poly$ is seen by at least one guard $g\in G$. Each guard corresponds
to a point in the polygon \poly, and we say that a guard $g$
\emph{sees} a point $p$ if the line segment $pg$ is contained in
\poly.
The art gallery problem has stimulated a myriad of research in
combinatorics and in algorithms. However, despite extensive research,
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 a complexity
class \ER. The class \ER consists of problems that can be reduced in
polynomial time to the problem of deciding whether a polynomial
equation with integer coefficients and any number of real variables
has a solution. It can be easily seen that $\NP\subseteq \ER$, and
there are reasons to believe that this inclusion is proper. We show
that the art gallery problem is \ER-complete, and thus we settle the
complexity status of this by now $44$ years old problem.
The \ER-hardness of the art gallery problem can be seen as an
explanation for the lack of satisfying algorithmic results.
Furthermore, it rules out many geometric approaches to solving the
problem.

joint work with: Mikkel Abrahamsen and Anna Adamaszek

---