Interestingly, it is actually very tough to find any positive algorithmic results on the art gallery problem. It seems like the art gallery problem is almost impenetrable.
For instance, only in 2002, Micha Sharir pointed out that the problem was even decidable [1]}, [2]}.
The decidability of the art gallery problem is actually easy once you know methods from real algebraic geometry [3]}.
The idea is to reduce the problem to the first-order theory of the reals.
We encode guard positions by variables, and then we check if every point in the polygon is seen by at least one guard.
Note that this is easy to encode in the first-order theory of the reals, as we are allowed to use existential (\(\exists g_1,g_2,\ldots \) ) and universal quantifiers (\(\forall p =(x,y)\) ).
Since then, despite much research on the art gallery problem, no better algorithm appeared, as far as worst-case complexity is concerned.
The underlying reason for the difficulty to find better algorithms
can be explained by the fact that the art gallery problem is \(\exists \mathbb {R}\) -complete [4]}, [5]}.
In a nutshell, \(\exists \mathbb {R}\) -completeness precisely entails that there is no better method for the worst-case complexity of the problem.
(\(\exists \mathbb {R}\)  can be defined as the class of problems that are equivalent to finding a real root to a multivariate polynomial with integer coordinates. See sub:ETR for an introduction.)
More specifically, it was shown that arbitrary algebraic numbers may be needed to describe an optimal solution to the art gallery problem.
This may come as a surprise to some readers, and was clearly a surprise back then.
Specifically, “in practice”, it seems very rare that irrational guards are ever needed.
The reason is that a typical situation is one of the following two.
Either the guards have some freedom to move around and still see the entire polygon.
Or if a guard has no freedom, it is forced to be on a line defined by vertices of the polygon.
As the vertices of the polygon are at rational coordinates, the guards will be at rational coordinates in that case as well.
Indeed, only in 2017, the first polygon requiring irrational guards was found [6]}.
Even though \(\exists \mathbb {R}\) -reductions exhibit an infinite number of polygons that require irrational guards, those polygons are not “concrete” in the naive sense of the word.
And up to this day, this is the only “concrete” polygon [6]} that we know does require irrational guards.
In this work, we find a second polygon.
It is superior to the first one in the sense that it shows that
two guards are already enough to enforce irrational guards.
As a single guard can always be chosen to have rational coordinates,
we settle the question of the minimum number of guards required to
have irrational guards.
We summarize our results in the following theorem.
