论文标题
点 - 边框美术馆问题是$ \已存在\ mathbb {r} $ - 硬
The Point-Boundary Art Gallery Problem is $\exists\mathbb{R}$-hard
论文作者
论文摘要
我们解决了美术馆问题的点界变体的复杂性，表明它是$ \的\ mathbb {r} $ - 完整的，这意味着它在多项式时间减少下是等效的，以确定多项式方程系统是否具有真实的解决方案。美术馆问题询问{\ it守护}是否有一种配置，可以看到{\ it Art Gallery}内部的每个点都以简单的多边形为模型。此问题的原始版本（我们称为点点变体）被证明是$ \ comests \ mathbb {r} $ - 硬[Abrahamsen，Adamaszek和Miltzow，JACM 2021]，但是该变体的复杂性只需要守卫即将守护艺术画廊的墙壁，就留下了一个开放的问题。我们表明，此变体也存在$ \ Mathbb {r} $ - 硬。我们的技术也可以用来极大地简化$ \的证明\ Mathbb {r} $ - 点点美术馆问题的硬度。以前工作中的小工具只能通过使用计算机来找到具有特定代数属性的复杂有理坐标。我们所有的小工具都可以手工构造，可以通过简单的几何参数进行验证。
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. Our techniques can also be used to greatly simplify the proof of $\exists\mathbb{R}$-hardness of the point-point art gallery problem. The gadgets in previous work could only be constructed by using a computer to find complicated rational coordinates with specific algebraic properties. All of our gadgets can be constructed by hand and can be verified with simple geometric arguments.
