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

Understand

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 classical problem in computational geometry.
• 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\in P$ is seen by at least one guard $g\in G$.
• Each guard corresponds to a point in the polygon $P$, and we say that a guard $g$ sees a point $p$ if the line segment $pg$ is contained in $P$.