The Point-Boundary Art Gallery Problem is $\exists\mathbb{R}$-hard

Understand

We resolve the complexity of the point-boundary variant of the art gallery problem, showing that it is $\exists\mathbb{R}$-complete, meaning that it is equivalent under polynomial time reductions to deciding whether a system of polynomial equations has a real solution.

• The art gallery problem asks whether there is a configuration of {\it guards} that together can see every point inside of an {\it art gallery} modeled by a simple polygon.
• The original version of this problem (which we call the point-point variant) was shown to be $\exists\mathbb{R}$-hard [Abrahamsen, Adamaszek, and Miltzow, JACM 2021], but the complexity of the variant where guards only need to guard the walls of the art gallery was left as an open problem.
• We show that this variant is also $\exists\mathbb{R}$-hard.