简单多边形中两个守卫的max-min算法研究

摘要

两个守卫(two-guard)问题是计算几何中的重要研究课题之一,由于很多实际问题都可以转化为平面内的几何模型进行求解,两个守卫的搜索区域以平面内的简单多边形为模型,在它的边沿上有一个入口s和一个出口t,两个守卫(two-guard)问题要求守卫从入口s出发,对多边形区域内的目标(非法入侵者)进行监视,并将其从出口t驱逐出去。对于此类问题的探索研究,为更多实际应用问题的解决提供了新思路和新方法,具有重要的理论意义和实际应用价值。
　　 本文对简单多边形中两个守卫的max-min问题即两个守卫的最大可视距离达到最小的问题进行了深入研究,对计算几何中的相关基础理论以及经典守卫问题进行了论述,研究了可直扫描多边形所具有的特性,分析讨论构成原子扫描的几种情形以及最优直扫描划分为若干个原子扫描的构造过程,并分别给出构造关键扫描线段和原子扫描的方法,从而构造得到原子扫描图,应用到max-min问题的求解算法中。最后,探索研究设计相应的数据结构,用来存储给定多边形内所有可能的原子扫描以及他们之间的转换关系,具体实现该算法,并验证算法的可行性和有效性,对实现结果做较为详细的分析。
　　 通过应用迪杰斯特拉算法处理原子扫描图,给出一个时间复杂度为O(n2logn)的算法,确定一个最优直扫描方案,为进一步研究的开放问题提供理论基础。