（计算机科学与技术专业论文）简单多边形中两个守卫的minsum算法研究.pdf

t r e s e a r c hm i n a l g o r i t h mo ft w og u a r d si nthehe r e s e a r c l l0 nm l n - s u ma l g o r i t h mt w og u a r a si nel s i m p l ep o l y g o n at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g b y l iy u j u a n ( c o m p u t e rs c i e n c e & t e c h n o l o g y ) t h e s i ss u p e r v i s o r ：p r o f e s s o rj i a n gb o m a y ，2 0 1 1 删f f f 刖洲川7 f i 川 y 1 8 9 6 61 。5 l i l i l l 。 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文兰篮垫多边垄生殖仝空卫曲婴i 卫：墨坚幽簦这婴究：。除论文 中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均己在文 中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公 开发表或未公开发表的成果。本声明的法律责任由本人承担。 l ， 学位论文作者签名：继 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密口( 请在以上方框内打“ ) 论文作者签名：苍玉 中文摘要 摘要 两个守卫( t w o g u a r d ) 问题是计算几何中的经典问题之一，它的主要研究议 题是：对于一个给定的简单多边形p ，在它的边沿上有一个入口s 和一个出口t ， 该多边形p 被称作走廊。t w o g u a r d 问题要求守卫从入1 2 1j 出发，把目标( 指非法 入侵者) 从出口t 驱逐出去。这类守卫问题是由著名的画廊问题和巡视员路径问题 激发而来，该类问题致力于在一个n 边形p 中用一组移动的守卫检测一个不可预 测的、移动的目标。 本文对t w o g u a r d 问题中的子问题m i n s u m 问题即简单多边形中两个守卫走过 的距离的总和达到最小的问题进行了深入研究。由于一台机器人( 或守卫) 需要的能 量和成本是它所移动距离的递增函数，所以研究m i n s u m 问题具有十分重要的价 值。 首先，研究计算几何领域中的相关基础知识；其次，论述计算几何中的经典 守卫问题，如画廊问题、最短巡视员路径问题以及t w o g u a r d 问题：再次，研究 t w o g u a r d 问题中的两种基本扫描方式，即直扫描和反扫描，论述相关扫描机理， 并分别给出在直扫描和反扫描情况下获得控制射点的几种情形，并构造射线段图， 应用到m i n s u m 问题的求解方法中；最后，针对m i n s u m 问题，探索一个最优扫 描方案，设计相应的数据结构并具体实现该算法，验证该算法的可行性和有效性， 对实现结果做较为详细的分析。 关键词：计算几何；t w o - - g u a r d 问题；简单多边形；min - s u m 算法；射线段图 英文摘要 a b s t r a c t t w o g u a r dp r o b l e mi so n eo ft h et y p i c a lp r o b l e m si nc o m p u t a t i o n a lg e o m e t r y i t s m a i nr e s e a r c ht o p i ci sa sf o l l o w s as i m p l ep o l y g o npw i t ha ne n t r a n c esa n da ne x i tt o ni t sb o u n d a r yi sc a l l e dac o r r i d o r t h ep r o b l e mo fs w e e p i n gc o r r i d o r sw i t ht w og u a r d s a s k st h eg u a r d st os t a r ta tt h ee n t r a n c esa n df o r c et h et a r g e to u to ft h er e g i o nt h r o u g h t h ee x i tt t h e s et y p e so fg u a r dp r o b l e m sa r em o t i v a t e db yt h er e l a t i o n st ot h e w e l l k n o w na r tg a l l e r ya n dw a t c h m a nr o u t ep r o b l e m s t h e ya l ed e v o t e dt od e t e c ta n u n p r e d i c t a b l e ，m o v i n gt a r g e ti na nn - s i d e dp o l y g o npb yag r o u po fm o b i l eg u a r d s t h i sp a p e rw i l lg i v eaf u r t h e rr e s e a r c ht om i n - s u mp r o b l e mo ft h et w o - g u a r d m o d e lp r o b l e m st h a tt h es u mo ft h ed i s t a n c e st r a v e l l e db yt h et w og u a r d si nt h es w e e pi s m i n i m i z e di nas i m p l ep o l y g o n t h em o t i v a t i o nf o rs m d y i n gt h i sp r o b l e ma r i s e sf r o m t h ef a c tt h a tt h ec o s to re n e r g yr e q u i r e db yam o b i l er o b o t ( g u a r d ) i sa ni n c r e a s i n g f u n c t i o no ft h ed i s t a n c ei tt r a v e l l e d f i r s t ，t h i sp a p e rr e s e a r c h e ss o m er e l e v a n tb a s i ck n o w l e d g eo fc o m p u t a t i o n a l g e o m e t r y t h e ni n t r o d u c et h ec l a s s i cg u a r dp r o b l e m s ，i n c l u d ea r tg a l l e r y , w a t c h m a n r o u t ea n dt w o g u a r dp r o b l e m s t h e nw es t u d yt h et w ob a s i cs w e e p s ：s t r a i g h ts w e e p a n dc o u n t e rs w e e p ，a n dg i v er e s p e c t i v e l ys e v e r a lw a y so fo b t a i n i n gc o n t r o ls h o t si n s t r a i g h ts w e e pa n dc o u n t e rs w e e p t h e n ，w eb u i l du pr a y s h o o t i n gs e g e m e n td i a g r a m ， a n da p p l yi tt os o l v em i n s u mp r o b l e m a tl a s t ，e x p l o r ea no p t i m u ms w e e ps c h e d u l ef o r m i n s u mp r o b l e m ，a n dd e s i g nc o r r e s p o n d i n gd a t as t r u c t u r ea n di m p l e m e n tt h ea l g o r i t h m t h e nv e r i f yt h ef e a s i b i l i t ya n dv a l i d i t yo ft h ep r e s e n t e da l g o r i t h m f o rr u n n i n gr e s u l td o m o r ed e t a i l e da n a l y s i s k e yw o r d s ：c o m p u t a t i o n a lg e o m e t r y ；t w o - g u a r dp r o b l e m ；s i m p l ep o l y g o n ； m i n - s u m a l g o r i t h m ；r a y s h o o t i n gs e g e m e n td i a g r a m 目录 目录 第l 章绪论1 1 1 研究背景与意义1 1 2 国内外的研究现状2 1 3 主要研究内容4 1 4 论文的组织结构4 第2 章t w o g u a r d 问题的相关理论基础6 2 1 计算几何及其经典计算几何问题6 2 1 1 计算几何的相关概念6 2 1 2 艺术画廊问题7 2 1 3 最短巡视员路径问题9 2 2t w o g u a r d 问题1l 2 3 预备知识。12 2 3 1 基本定义1 2 2 3 2 可扫描简单多边形1 8 第3 章m i n s u m 问题的求解分析2 2 3 1 射线段之间的基本扫描。2 2 3 1 1 直扫描2 2 3 1 2 反扫描2 7 3 2m i n s u m 问题2 9 3 2 1 射线段图的构造2 9 3 2 2m i n s u m 问题的求解算法3 1 3 3 一个下界3 4 第4 章求解m i n s u m 问题的算法实现3 6 4 1 算法思路3 6 4 2 数据结构3 9 4 3 算法实现。4 l 第5 章运行结果及其分析4 7 5 1 测试数据分析。4 7 5 2 运行结果分析。4 9 第6 章总结与展望5 3 6 1 论文工作总结5 3 目录 6 2 进一步研究工作5 4 参考文献。5 5 致谢5 9 研究生履历6 0 简单多边形中两个守卫的r a i n s h i n 算法研究 第1 章绪论 1 1 研究背景与意义 艺术画廊问题是计算几何中的经典问题之一，在现实生活中具有很大的研究 和应用价值。1 9 7 3 年，v i c t o rk l e e 首次提出了该问题，具体描述为：在画廊中设 置多个守卫( 摄像机) ，以保证画廊内每一个角落至少可以被一个守卫监视到( 其视 线无法穿透墙壁，视角为3 6 0 0 ) ，问题的目标是如何使守卫的数量达到最少【i 】。现 实生活中有很多实际问题都可以归结为艺术画廊问题，而艺术画廊问题也有很多 变形的描述。c h v a t a l 2 1 和f i s k t 3 1 等人所首先研究的最少巡视员( m i n i m 啪w a t c h m e n ) 问题就是这类问题中的一个例子，其描述为：在某给定区域( 一般被抽象为一个简 单多边形) ，计算出最少数量的巡视员( 巡视员是静止的) ，使得该区域的边沿( 如墙 壁) 上的每一个点至少能够被一个巡视员检测到。这个问题也被称为巡视员问题， l e e 和l i n t 4 】在其研究文献中给出了求解该问题的复杂度分析。 巡视员问题的另一个研究方向是最短巡视员路径问题，也是计算几何研究中 更常见的最优化问题。最优化的目标是在多边形区域内寻找巡视员( 巡视员是动态 的) 所要经过的一条闭合曲线( 路径) ，该路径是最短的，并保证巡视员可以看到区 域内的每一个角落，也就是说，简单多边形内壁的每一个点都至少能够被该路径 上的一个点检测到。该问题最早由c h i n 和n t a f o s 在1 9 8 8 年提出，后来引起了广 泛的研究。关于艺术画廊问题( 也称画廊问题) 以及许多相关问题的研究，在 o r o u r k e 的文献 5 】中有比较全面的论述。 受画廊问题和最短巡视员路径问题的启发，近年来，研究人员将注意力集中 到了两个守卫( t w o g u a r d ) l h 题上。该问题的一般描述为用一组移动的守卫来检测一 个刀边形p 内一个无法预测的、移动的目标( 指非法入侵者) ，守卫的目的是无论该 目标移动得有多快，守卫要么始终能看得到该目标，要么证实该多边形内没有目 标出现。当守卫的个数为2 时，即为著名的t w o g u a r d 问题。关于多边形形状以及 作为守卫的可视传感器的论述在文献 6 】和文献 8 1 5 1 0 0 都有比较详细的描述。 第1 章绪论 t w o g u a r d 问题的实例随处可见。例如，在一条具有危险的市中心街道上，两 个警察必须分别沿着街道的两边进行搜索，每个警察负责检查自己所属的那一边 的所有银行的门。问题是：用这种方式进行搜索的守卫能否总是互相看得见呢? t w o g u a r d 问题的要求是两个守卫能够相互可见。本文的研究目标是在一个简单多 边形中寻找一个最优扫描( 搜索) ，使得扫描中的两个守卫点相互可见且扫描的距 离总和要达到最小。本文将这个问题称为m i n - s u m 问题。对于人类而言，m i n s u m 问题的实现可能比较简单，因为他们可以通过语言通讯来实现两者之间的协调搜 索；但对于机器人而言，求解该问题就存在一定的难度。那么，机器人如何找到 这样的一个最优扫描来完成对指定区域搜索呢? 本文将针对这个问题展开较为深 入的研究。 本文的研究目标是寻找一个最优扫描，使得两个守卫在扫描过程中保持互相 可见且走过的距离总和达到最小。针对该问题的研究不仅在理论上具有重要的意 义，在应用领域也有重要的作用。由于一台机器人( 或守卫) 需要的能量和成本是它 所移动距离的递增函数，所以研究m i n s u m 问题就具有十分重要的价值。m i n - s u m 问题的研究结果具有广泛的应用前景，例如，战地机器人、反战装置和视频监视 器等方面，都可以应用该研究成果来提升应用性能，降低应用成本。在战争情况 下，可给定起始位置和终止位置，然后为战士( 或机器人) 规划出一条最优扫描( 监 视) 路径，使得在整个移动过程中，两名战士( 或机器人) 总是彼此可见，并且使得 两者移动的距离总和最小。前者提升了战士的安全性，后者则最大限度地节省了 所耗费能量和成本。 1 2 国内外的研究现状 i c k i n g 和k l e i n 首先研究了两个守卫扫描通道的问题，该问题被称作t w o g u a r d 问题【6 】。通道可以抽象为一个简单多边形尸，在它的边上有一个入口s 和一个出口 t 。两个守卫扫描通道的问题的具体描述就是要求守卫从入口j 处开始，把目标( 可 以设想为非法入侵者) 从出口t 驱逐出该多边形区域【6 】。文献 6 给出了一个时间复杂 度为o ( n l o g n ) 的算法，用以判定两个守卫能否扫描给定的通道。1 9 9 6 年，h e f f e m a n 2 简单多边形中两个守卫的m i n s u m 算法研究 给出了一个线性时间的算法吲。t s e n g 等人则给出了一个o ( n l o g n ) 时问复杂度的算 法来判断在多边形p 中是否有一对顶点支撑一个扫描。2 0 0 1 年，这个结果被改进 为o ( n ) 时间复杂度内完成相应的扫描【8 】。如果两个守卫能够扫描给定的通道，那 么，就能够在o ( n l o g n + 聊) 时间复杂度内给出一个包含最少数量m 的扫描规则， 其中，m 有一个下限，可记为n ( n 2 ) 【6 1 。 用两个守卫点扫描简单多边形的问题后来被广为研究【9 , 1 0 】，其中，多边形边上 的出口和入口都没有预先给出，任一扫描方案的起始点都有可能不止一次地被目 标访问，这种现象被称为“再污染”。也就是说，对于一系列守卫点的扫描简单多边 形的问题，再污染现象是不可避免的【1 0 , 1 1 , 1 6 】。再污染现象使得该问题的求解变得更 加困难，也更有挑战性。在此之前的研究主要集中在对于给定的多边形判断是否 存在一个扫描，并且在能够扫描的情形下给出具体扫描方案。例如，文献【1 l 】和文 献 1 6 中分别提出了一个时间复杂度为线性的判定两个守卫能否扫描一个简单多 边形的算法和一个时间复杂度为o ( n 2 ) 的扫描方案。 近年来，关于守卫扫描( 搜索) 多边形区域的研究成果种类越来越多。2 0 0 0 年， l e e 等人针对一个搜索者( 守卫) 搜索( 扫描) 带有一扇门的多边形房间问题进行了研 究，给出了一个o ( n 2 ) 时间复杂度的算法，用来构造一个搜索方梨1 。丌。2 0 0 1 年， 同样基于一个搜索者，s a n g - m i np a r k 等人则给出了判定一个多边形是否可搜索的 简单有效的条件，并证明每一个可搜索的多边形也能被一个装备有两个手电筒的 搜索者搜索【1 6 】。2 0 0 4 年，xt a n 针对两个守卫( t w o g u a r d ) l h 题的再访问和一般化进 行了研究，并将t w o g u a r d 问题的解决方法延伸到t h r e e g u a r d 问题上，在o ( n l o g n ) 时间复杂度内给出一个扫描方案【墙l 。在2 0 0 5 年t a n 也针对一个搜索者搜索多边形 区域进行了研究，给出了一个o ( n l o g n ) 时间复杂度和o ( n ) 空间复杂度的算法，用 来判断一个简单多边形的可搜索性【1 2 】。随后，t a n 也研究了用一组守卫来扫描简单 多边形的问题，给出了o ( n 2 ) 时间复杂度的算法来计算检测目标所需的最小数量为 厂宰的守卫。并且，该扫描方案能在o ( f * v 1 2 ) 时间复杂度内给出【9 1 。2 0 0 8 年，t a n 和j i a n g 对两个守卫扫描一个多边形区域进行研究，根据非冗余组件，给出了两个 3 第1 章绪论 守卫可扫描的多边形的特征，以及判定两个守卫是否能扫描该多边形的一个o ( n ) 时间复杂度的最优算法【10 1 。如果该多边形区域可扫描，那么，就能在o ( n l o g n + m ) 时间复杂度内给出一个扫描方案，其中，n 是多边形的顶点数，m ( ，1 2 ) 是扫描规 则数。针对简单多边形中两个守卫的扫描距离总和最小的问题，近几年的研究文 献并没有更新的研究成杲。原t w o g u a r d 问题对于扫描距离最小的算法经典但复杂， 基于前人的研究成果，通过积极研究探索，给出本文关于m i n s u m 问题的研究成 果。 1 3 主要研究内容 本文针对计算几何中一些多边形的扫描问题、可视问题进行研究，这些问题 包括画廊问题、最短巡视员路径问题和t w o g u a r d 问题等，并着重研究t w o g u a r d 问题中m i n s u m 问题的相关理论与求解方法，给出求解该问题的具体算法并对实 现结果进行分析。具体而言，本文的主要研究内容包括如下几个方面： ( 1 ) 研究计算几何领域中的相关基础知识，包括定义、概念，以及相关原理等， 为本文的研究课题奠定坚实的理论基础。 ( 2 ) 研究计算几何中的经典守卫问题，包括画廊问题、最短巡视员路径问题以 及t w o g u a r d 问题等。 ( 3 ) 研究t w o g u a r d 问题中的两种基本扫描方式，即直扫描和反扫描，论述相 关的扫描机理，为求解m i n s u m 问题奠定基础。 ( 4 ) 研究t w o g u a r d 问题中的现有算法，依据这些算法的基本机理与算法思想， 探索求解m i n s u m 问题的基本思路。 ( 5 ) 针对m i n s u m 问题，探索一个最优扫描方案，并基于v c + + 开发平台，设 计相应的数据结构并具体实现该算法，并验证算法的可行性与有效性，对实现结 果做较为详细的分析。 1 4 论文的组织结构 根据本文的主要研究内容，拟将本文分为6 章分别加以论述。 4 简单多边形中两个守甲的m i n - s l l m 算法研究 第1 章绪论。本章论述本课题的研究背景与意义、国内外研究研究现状和 m i n s u m 问题及其应用，并对本文的研究内容和论文组织结构进行概述。 第2 章t w o g u a r d 问题的相关理论基础。本章主要论述计算几何中经典守卫问 题，包括画廊问题、最短巡视员路径问题以及t w o g u a r d 问题等。另外，对t w o - g u a r d 问题的基础概念、定义和性质做较为详细的论述。 第3 章m i n s u m 问题的求解分析。本章对t w o g u a r d 问题的子问题m i n s u m 问题进行深入的研究，详细论述两种基本扫描方式，分别给出在直扫描和反扫描 情况下获得控制射点的几种情形，并构造射线段图用于求解m i n s u m 问题。 第4 章求解r a i n s u m 问题的算法实现。经过对m i n s u m 问题的分析与研究， 本章论述求解该问题的算法实现，并详细论述算法实现中的数据结构、部分重要 的程序代码等。 第5 章运行结果及其分析。本章对本文所给出算法的运行结果进行分析，并 验证该算法的可行性和有效性。 第6 章总结与展望。本章对论文的工作进行总结，并提出进一步的研究展望。 5 第2 章t w o g u a r d 问题的相关理论基础 第2 章t w o - g u a r d 问题的相关理论基础 本章着重论述t w o g u a r d 问题研究中所涉及到的相关理论基础，包括经典计算 几何的相关问题，以及求解m i n s u m 问题时所需要的一些基础知识与相关概念。 2 1 计算几何及其经典计算几何问题 t w o g u a r d 问题是计算几何中一个经典的问题，在解决该问题的过程中涉及到 了计算几何中的一些基础问题，因此有必要从计算几何的相关基础知识开始，分 别加以论述。 2 1 1 计算几何的相关概念 计算几何学是在自2 0 世纪7 0 年代末期从算法设计与分析中独立出来的一个 研究领域，它是计算机理论科学的一个重要分支。1 9 7 5 年，s h a m o s ( 沙莫斯) 和 h o e y ( 霍伊) 利用计算机有效地计算出了平面点集的v o r o n o i 图，并发表了一篇著名 论文，从此计算几何诞生t t l9 1 。 随着计算几何的诞生以及计算几何领域的相关研究工作的进展，使得计算几 何成为理论计算机科学领域中一个新的极有生命力的领域，计算几何中的研究成 果在计算机图形学、化学、统计分析、模式识别、地理数据库以及其他许多领域 中也得到了广泛的应用。如今，计算几何已经成长为一个被广泛认同的学科，既 拥有自己的学术会议和学术刊物，又形成了一个由众多优秀活跃的研究人员组成 的学术群体。该领域作为一个新兴的学科之所以会取得成功，一方面是因为它所 研究的问题及其解决方法本身所具有的美感；另一方面也是由于它在( 诸如地理信 息系统、计算机图形学和机器人学等) 众多应用领域中发挥着重要作用。 计算几何研究的典型问题包括几何基元、优化、查找等问题类【1 9 1 。首先，几 何基元包括凸壳和v o r o n o i 副2 0 1 、多边形的三角剖分【2 、划分问题与相交问题； 其次，几何优化包括参数查找和线性规划；再次，几何查找包括点定位、可视化、 区域查找等问题；此外，计算几何中各种问题的下界确定、推导下界的方法以及 求解各类几何问题的算法的复杂性分析等，也是计算几何研究的主要内容。 6 简单多边形中两个守卫的m i n - s u m 算法研究 计算几何的最新发展包括计算实代数几何、几何抽样理论、运动规划、计算 拓扑、并行计算几何、隐藏面的移动、结构和图形、网络生成以及计算机视觉中 的几何问题等【1 9 】。它也逐步涉及到计算理论、计算机辅助设计、计算机图形学、 机器入学、地理信息系统、c a d c a m 等相关领域的研究工作中。计算几何学所涉 及的应用领域可用图2 1 加以简单描述。 图2 1 计算几何学的应用领域 f i g 2 1t h ea p p l i c a t i o na r e ao fc o m p u t a t i o n a lg e o m e t r y 目前，计算几何学已经成为一个庞大的学科领域，其中一部分待解决的问题 是关于简单几何图形的，其解决方法种类多样，各有侧重，且包含退化情形和浮 点精确度等。这些问题包括凸多边形( c o n v e xh u l l ) 、交点问题( i n t e r s e c t i o np r o b l e m ) 、 机器人问题( r o b o t i c sp r o b l e m ) 、线段交点( l i n es e g m e n ti n t e r s e c t i o n ) 、平面、多边 形、画廊问题( p l a n a rg r a p h s ，p o l y g o n sa n da r tg a l l e r i e s ) 、最短路径( s h o r t e s tp a t h s ) 竺【2 2 】 寸 o 2 1 2 艺术画廊问题 面对出自名家手笔的价值不菲的绘画艺术品，怦然心动的可不只是艺术爱好 者，罪犯们也是如此。为了防止作品被盗，必须对其画廊内的作品严加看管。在 白天，值班人员可以担负起看守的任务，可是到了晚上，在为了节省人力，但同 时也不能放松戒备的情况下，这项工作就只能落在摄像机身上了。一般而言，这 些摄像机都被挂在天花板上，能够绕着一个垂直轴做3 6 0 0 的旋转。这样，利用摄 7 第2 章t w o - g u a r d 问题的相关理论基础 像机，夜间值班人员就能通过电视屏幕对艺术画廊进行监控。显然，所安排的摄 象机数量越少，其成本也就越小，值班人员的负担也就越轻松。因此，研究本问 题的一个基本目标是要尽可能地减少摄像机的数量。另一个方面，摄像机的数目 也不可能太少，因为画廊内的每一个角落都必须能够被至少一台摄像机的视野所 覆盖到【1 1 。 图2 2 艺术画廊问题的示意图 f i g 2 2s c h e m a t i cd i a g r a mo fa r tg a l l e r yp r o b l e m 显然，摄像机的安装位置很有讲究，为了减少摄象机的数量，应该使每台摄 像机在画廊中都能覆盖尽可能大的范围。这个问题被学术界定义为艺术画廊问题 ( a r tg a l l e r yp r o b l e m ) ，也是计算几何中的经典问题，它可用图2 3 来抽象地进行描 述。问题是，给定一个画廊，至少需要多少台摄像机? 应该将它们分别安装在什 么位置呢? 问题的求解目标是既要能够覆盖整个画廊，又要使摄像机( 也被称为守 卫) 的数量达到最少，以节省人力、物力资源。 图2 3 监视画廊的一组摄像机 f i g 2 3ag r o u po fc a m e r a sm o n i t o r i n gt h eg a l l e r y 简单多边形中两个守卫的m i n s u m 算法研究 为了方便研究，通常将艺术画廊问题做形式化的处理，即将该问题限制在平 面上，用一个平面结构图来表示，将画廊的墙壁看做是一条边，因而整个艺术画 廊就可以形式化为一个简单多边形。于是，在既经济，又能全面覆盖该多边形的 条件下，至少应该需要安装多少台摄像机? 又分别在哪里安装呢? 艺术画廊问题的更为形式化的描述为：给定一个具有n 个顶点的简单多边形 p ，在p 的边界或其内部寻找一个点集s ，s = m i n ul u 覆盖p ) 。艺术画廊问题 的研究目标是找到最少的子集来覆盖整个多边形【2 2 1 。 在1 9 7 3 年，k l e e 与v a s e kc h v a t a l 在一次交谈中提出了艺术画廊问题。c h v a t a l 后来提出，在具有n 个顶点的简单多边形中，至多可找到ln 31 个点，从这些点足 以看到多边形内的每一个剧1 1 。自从这个定理发表后，计算机科学界和数学界展开 了大量关于照明和画廊问题的研究。1 9 8 4 年0 r o u r k e 2 3 】撰写了画廊定理与算法 一书，这本书极大地推动了画廊问题的研烈2 4 】。画廊问题有许多变形，如带洞区 域的画廊问题，视角受限的画廊问题，m 巡视员路径问题等，文献 2 5 3 0 分别论 述了画廊问题的一些研究成果。 画廊问题中，摄像机( 或守卫) 的位置是固定不动的，只是允许有3 6 0 0 的视角。 如果考虑画廊问题中的守卫具有移动性，并且守卫的移动范围是整个多边形区域， 那么，画廊问题就演变为巡视员路径问题。巡视员路径问题不会限制守卫的移动 路径，只要求在简单多边形内部移动的路径总和达到最短。 2 1 3 最短巡视员路径问题 最短巡视员路径问趔3 i 】最早由c h i n 和n t a f o s 在1 9 8 8 年提出，它属于计算几 何中的最优化问题，是在画廊问题和旅行商问题( t s p ) 【3 2 】的研究推动下提出的。该 问题一经提出，就有很多研究人员对此进行了深入的研究弘3 引。最短巡视员路径 问题的最优化目标是计算在多边形区域内巡视员所经过的路径为最短，并要求路 径为一条闭合的曲线且保证巡视员可以看到区域内的每一个位置点，也就是说， 在简单多边形内部的任意点，都至少能被该最短路径上的一个点监视到。对于一 个给定的简单多边形，巡视员所走的最短巡视路径的一个例子如图2 4 所示。最短 9 第2 章t w o - g u a 一问题的相关理论基础 巡视员路径问题和画廊看守问题所研究的共同目标是监视整个给定的多边形区 域，不过，画廊问题在基于可视性的基础上增加了测度信息【3 9 1 。 图2 4 巡视员最短巡视路径的例子 f i g 2 4t h ee x a m p l eo fw a t c h m a n ss h o r t e s tw a t c h i n gr o u t e 最短巡视员路径问题也可以用数学语言来描述：给定一个具有n 个顶点的简单 多边形p ，在p 的内部寻找一条最短闭合曲线形，使得对于任意p p ，都存在一 个点q 形，使得线段p q 在p 的内部，即p 和g 是相互可见的 4 0 1 。 为求解最短巡视员路径问题，一般可将该问题分为两种情形：一种情形是指 定起始点，该起始点位于简单多边形的边界上，所求解的最短路径必须经过该起 始点；另一种情形是不设定起始点，在这种情况下，最短巡视员路径问题也被称 作最短移动w p r ( w a c h m a nr o u t ep r o b l e m ) t 4 。 随着对最短巡视员路径问题研究的不断进展，并考虑到现实生活中的不同应 用，最短巡视员路径问题出现了许多变形，对巡视员最短路径问题及其变形问题 的求解方法也适用于机器人或人选择最合适的路线，例如，在发生火灾时，可通 过对建筑物进行分析，让救援机器人进入建筑物内寻找被困人员，运用多边形搜 索算法，能够以较小的代价并及早地发现被困人员。 1 0 简单多边形中两个守卫的m i i l - s u m 算法研究 2 2t w o - g u a r d 问题 由画廊问题和巡视员路径问题的诱发，守卫问题开始在越来越多的研究文献 中出现。t w o g u a r d 问题便是在这个时期被提出来的。该问题可以形象地描述为： 在市中心一条危险街道上有一对巡逻的警卫。每一名巡警必须分别沿着街道两边 的人行道巡逻。一直到街道的尽头，去检查自己所在边的所有银行的门。两名守 卫以这样的方式向前行进，他们能否总是看到彼此呢? 如图2 5 所示，黑色粗线条 代表街道旁的建筑物，形成一个包含一对出入m ( s 和g ) 的多边形区域。 假设给定一个拥有力条边和包含两个重要顶点s 和g 的一个简单多边形尸，顶 点s 和g 将多边形p 分成了两个互不相交的链，每个链由若干条p 的边构成。在尸 的两个链上的两个移动点( 守卫) ，能否分别从s 移动到g 且在移动过程中始终保持 连接两个移动点的线段完全包含在多边形内呢? 移动过程中，允许每个移动点沿 原路倒退，但最终这两个移动但都必须都到达顶点g 。具有这些约束的一个移动问 题被称为一个扫描。一个多边形如果存在一个这样的一个扫描，那么就说它是可 扫描的。在可扫描的情况下，人们更多的是关心两个守卫的移动距离总和达到最 小。 图2 5 两个守卫问题 f i g 2 5t h et w 伽g u a r dp m b l e m r 第2 章t w o - g u a r d 问题的相关理论基础 在两个守卫从s 点向g 点扫描的过程中，一种情形是约定守卫点在扫描过程中 不能沿原路返回，这样的扫描被称作直接扫描，简称直扫描。在直扫描中，连接 守卫点的线段有序地扫描该多边形；另一种情形是在扫描过程中，当一个守卫朝 着g 的方向前进时，另一个守卫必须按原路返回才能保证所指定的区域被完全搜 索，这种扫描被称作反方向扫描，简称反扫描。 t w o g u a r d 问题中，i c k i n g 和k l e i n 首先在直扫描情况下，给出了判定简单多边 形尸是否可直扫描的必要条件。进而给出判定这些必要条件和构建一个直扫描需 要o ( n l o g n ) 的时间复杂度和线性的空间复杂度；其次，在反扫描情况下，给出判 定简单多边形p 是否可反扫描的必要条件，进而证明构建一个反扫描方案需要在 o ( n l o g n ) 的时间复杂度内计算出来；最后，将这些结论用来解决一般扫描问题( 即 包含直扫描，又包含反扫描) ，提出在o ( n l o g n + k ) 时间复杂度内能计算出一个扫 描距离总和最小的扫描方案，其中，k 是两个守卫的扫描规则数( 本文用m 标记) 。 本文所研究的简单多边形中两个守卫的m i n s u m 问题，就是t w o g u a r d 问题的 子问题。本文尝试用一种新的研究方法来解决扫描距离总和最小的问题。该问题 有一个基本的约定，即两个守卫在给定的简单多边形的边上移动，两者始终保持 互相可见，且连接两个守卫的线段能将多边形p 分成一个“干净”区域( 已经搜索的 部分) 和一个“不干净”区域( 未搜索的部分) 。在这种情况下，一个首先要解决的问题 就是整个简单多边形p 是否是干净的，也就是说目标能否被检测到。如果能，则 该简单多边形是可以被完全搜索的。下面本文将陆续展开对m i n s u m 问题的研究。 2 3 预备知识 本节将给出在论文研究中所要用到的一些基本定义、概念以及符号。 2 3 1 基本定义 本文所讨论的两个守卫问题被限制在简单多边形中，也就是说，给定的简单 多边形内部不存在相交的边，也不含空洞。 定义2 1 ：由平面上若干条线段围成的封闭有界域称为多边形。其中，每条线 段称为多边形的边，相邻的两条边仅在端点相交，其交点称为多边形的顶点【拇l 。 1 2 简单多边形中两个守卫的m i n - s u m 算法研究 定义2 2 ：设平面上n 个点p - ，p ：，肼按循环排序方法逆时针排列，p l 在 p 之后，又设e l = p i p 2 ，e 2 = p 2 p 3 ，e n = p p l 是连接点的n 条线段，那么这些 线段构成一个简单多边形当且仅当( 1 ) 循环排序中相邻线段对的交是它们之间共 有的唯一顶点，即e l f 3 e i + i = p i + i ；( 2 ) 不相邻的线段互不相交，即e i n e j = g ， i + 1 ；待一1 , n ，e n + l _ e l ，p + l = p l 1 19 1 。 上述定义中，点p i 称为多边形的顶点，线段e i 称为多边形的边。以个顶点的多 边形必有刀条边。图2 6 给出了简单多边形与非简单多边形的一个例子【l 】。 ( a )( b ) 图2 6 简单多边形与非简单多边形