论文标题
反对半后卫
Opposing Half Guards
论文作者
论文摘要
我们研究对抗半后卫的美术馆问题：只能向左或右边看到的后卫。我们提出了美术馆定理，表明，在2守形多边形中，半守卫的位置不限于扩展，这表明该问题是单调多边形的NP-HARD，并且呈螺旋和楼梯多边形的近似算法。
We study the art gallery problem for opposing half guards: guards that can either see to their left or to their right only. We present art gallery theorems, show that the location of half guards in 2-guardable polygons is not restricted to extensions, show that the problem is NP-hard in monotone polygons, and present approximation algorithms for spiral and staircase polygons.
