Approximate Guarding of Monotone and Rectilinear Polygons
Approximate Guarding of Monotone and Rectilinear Polygons
复制标题
单调和直线多边形的近似守卫
作者：
Bengt J. Nilsson
证明了单调多边形的顶点保护是NP-困难的，并构造了单调多边形内部保护的常数因子逼近算法。利用这个算法，我们得到了一个近似算法的内部守护直线多边形，具有一个近似因子的多边形的顶点数无关。如果最小的内部保护覆盖的大小是OPT的直线多边形，我们的算法产生一个保护集的大小为O（OPT 2）。
We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is OPT for a rectilinear polygon, our algorithm produces a guard set of size O(OPT2).