Research On Algorithms Of Solving The Polygon Surveillance Problem

Along with the increasing people demand for security surveillance,how to station and utilize those monitors in a effective way become the focus.One topic of Computational Geometry which based on visibility and optimization can be regarded as Polygon Surveillance Problem(PSP).Therefore,it is very important to find the effective method to solve the PSP.For the various of Surveillant tools(guard or watchman),PSP can be divided into some sub-problems.For instance,the Art Gellary Problem(AGP),the Shortest Watchman Route Problem(SWRP) and m-Watchman Route Problem(m-WRP),etc.The PSP relate to a mount of Computational Geometry knowledges.firstly,we study some basic problems of Computational Geometry.Then,we induce the Computational complexity and approximation factor of solution algorithms for solving the AGP and the SWRP.With the research and analysis of those algorithms,two methods are proposed to solve the instance of vertex guard of AGP,one algorithm is based on the degree of internal angle,the other one use a filling method.Time complexity of those algorithms both are O(nr~2),we use some benchmark scene to verify the performance of the two algorithms.From the results,we can conclude that the Algorithms which we proposed can give the Optimal Solution or a O(1)-approximation for the AGP.