【作者】 王岩；

【导师】 蒋波；

【作者基本信息】 大连海事大学 ， 计算机软件与理论， 2008， 硕士

【摘要】 随着人们对安全监视需求的增加,如何有效地设置和使用监视器成为关注的焦点。本文将计算几何中一类基于可视性和最优化的问题定义为多边形监视问题,并针对如何求解这类问题进行了较为深入的研究。多边形监视问题由多个问题组成,根据监视工具(守卫、巡视员)的不同可以具体为画廊问题,最短巡视员路径问题,m-巡视员路径问题等。多边形监视问题的求解过程会涉及大量的计算几何相关知识,本文首先对计算几何基本问题进行了分析和研究。随后对画廊问题以及最短巡视员路径问题的现有求解算法的计算复杂度及近似程度进行了归纳,具体分析了几个典型算法的算法描述和计算复杂度。最后,针对画廊问题中的顶点守卫情形,给出了时间复杂度均为O(nr~2)的基于内角大小的求解算法和基于填补技术的算法。通过使用一些经典画廊场景对算法的有效性进行了验证与分析,结果表明,本文所设计的算法在绝大多数情况下,可以给出画廊问题的一个最优解,或以O(1)的近似比逼近最优解。更多还原

【Abstract】 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.更多还原