带权值目标点的可见覆盖求解算法

An Algorithm for Visible Covering of the Weighed Target Points

针对传统的艺术画廊模型及其模型的变形在实际应用中无法处理诸如可用守卫数受限、只需监控离散目标点等情形,提出一种基于带权值目标点的可见覆盖的变形模型及其求解算法.首先利用角扫描技术得到每个目标点的可见多边形,然后通过对这些可见多边形进行几何求交、几何求差操作来得到若干等价目标可见区域,再依据每个区域对应的可见目标点集将所提出的变形模型转化为经典的集合最大权值覆盖问题,最后利用整数线性规划方法对其求解,得到最终需要的守卫数及放置位置.大量的实验结果表明,该算法是正确和有效的.

Traditional art gallery problem （AGP） and its existing variations have some deficiencies in practical applications when the number of available guards is limited or the target is consisted of discrete points.In order to solve these problems,this paper proposes a new variation of AGP based on the covering of the weighed target points and corresponding algorithm.Firstly,it uses angular sweep method to get the visibility polygons of target points.Secondly,it uses geometric intersection and geometric difference operations to get the equivalent target visibility regions.Based on these regions,the new variation can be converted to the classic weighted maximum coverage problem.At last,integer linear programming is applied to get the final number of guards and their locations.Experimental results show the correctness and efficiency of the algorithm.