论文标题
关于半延伸单调多边形的复杂性
On the Complexity of Half-Guarding Monotone Polygons
论文作者
论文摘要
我们考虑了美术馆问题的一种变体，其中所有警卫都仅限于单调多边形内的右侧。我们称之为这样的警卫：半守护者。我们提供了多项式时间近似，用于守护整个单调多边形。我们将最著名的40个近似值从[11]提高到8。我们还提供了NP硬度，以守护用半导体的单调多边形。
We consider a variant of the art gallery problem where all guards are limited to seeing to the right inside a monotone polygon. We call such guards: half-guards. We provide a polynomial-time approximation for point guarding the entire monotone polygon. We improve the best known approximation of 40 from [11], to 8. We also provide an NP-hardness reduction for point guarding a monotone polygon with half-guards.
