多边形监视问题的求解算法研究

论文摘要

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

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究意义
• 1.3 研究内容
• 1.4 论文的组织结构
• 第2章 多边形监视问题的相关理论基础
• 2.1 多边形监视问题
• 2.1.1 画廊问题
• 2.1.2 最短巡视员路径问题
• 2.1.3 m-巡视员路径问题
• 2.2 计算几何基本问题
• 2.2.1 计算几何
• 2.2.2 相关专业术语及其定义
• 2.3 典型基础算法
• 2.3.1 顶点凹凸性判断
• 2.3.2 三角剖分
• 第3章 多边形监视问题的求解算法
• 3.1 问题计算复杂度
• 3.1.1 画廊问题的计算复杂度
• 3.1.2 最短巡视员路径问题的计算复杂度
• 3.2 画廊问题的求解算法
• 3.2.1 剖分方法解决画廊问题
• 3.2.2 基于多边形核的求解算法
• 3.2.3 对数近似比求解方法
• 3.2.4 其它求解算法
• 3.3 最短巡视员路径问题求解算法
• 3.3.1 相关定义及切割求解方法
• 3.3.2 SWRP精确求解算法
• 3.3.3 SWRP近似求解算法
• 第4章 求解算法的改进及其性能分析
• 4.1 设计思路
• 4.2 基于内角大小的算法
• 4.2.1 顶点优劣判断
• 4.2.2 基于内角大小的算法描述
• 4.3 填补算法
• 4.3.1 填补技术
• 4.3.2 填补算法描述
• 4.4 算法分析
• 第5章 算法实现与效率验证
• 5.1 数据结构
• 5.2 程序实现
• 5.2.1 凹凸性判断程序段
• 5.2.2 顶点相互可见判断
• 5.3 算法复杂度分析
• 5.3.1 基于内角大小算法复杂度分析
• 5.3.2 填补算法复杂度分析
• 5.4 运行实例及其结果验证
• 第6章 结论
• 6.1 论文工作总结
• 6.2 进一步的研究工作
• 参考文献
• 致谢
• 研究生履历