On the lower bound side, we know NP-hardness [1]}, APX-hardness [2]} and W[1]-hardness [3]}.
One may argue that NP-hardness is enough evidence that there are
no efficient algorithms for the art gallery problem and that this
may fully explain the lack of algorithmic results.
However, for other NP-complete problems like Clique, Subset-sum, Dominating Set, and TSP, we do know a myriad of algorithms.
Although many of them run in exponential time in the worst case they give huge improvements in many different situations.
We believe that the lack of algorithmic results may stem from the fact that
we do not know how to discretize the art gallery problem efficiently.
Note that all the mentioned problems are already discrete.
We believe that the \(\exists \mathbb {R}\) -completeness of the art gallery problem may give the most compelling explanation of why a concise discretization of the art gallery problem is unlikely [4]}, [5]}.
Specifically, many discretization schemes would imply that the art gallery problem lies in NP and thus imply \(\text{NP} = \exists \mathbb {R} \) .
The first proof that the art gallery problem is \(\exists \mathbb {R}\) -comlete was given by Abrahamsen, Adamaszek, and Miltzow in 2017 [4]}.
It was recently improved by Stade, who showed that it is even \(\exists \mathbb {R}\) -complete if we only require the boundary to be guarded [5]}.
It remains open whether guarding the boundary from the boundary is \(\exists \mathbb {R}\) -complete.
