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.