（应用数学专业论文）一个艺术画廊看守问题的启发式算法.pdf

中文摘要 摘要 艺术画廊问题来源于人们的现实生活 已经吸引了越来越多的学者对其进行 研究 如今 它在现实生活的很多领域中都有着重要的应用 由于求任一简单多 边形所需看守的最少数目 这一算法是n p 难的 所以人们尝试着给出求简单多边 形所需看守数目相对比较优的算法 本文提出了大部分具有k 个凹点的简单多边 形所需看守数目的一个启发式算法 一般情况下 此看守数目要要优于k 因此 无论在理论上还是在实际应用中 对其研究都具有一定的意义 本文的主要工作有 1 由艺术画廊定理可知 对于任意的多边形 其最小看守数为in 3i 在研究多边形所需监视器的数目中 多边形中的凹点起着非常重要的作用 由于 对绝大多数的具有k 个凹点的简单多边形来说 k 台监视器并不是最优的 所以 本文通过分析简单多边形的剖分及其算法 从凹点的角度出发 提出简单多边形 的m 形剖分以及m 形剖分的算法 并在此剖分及其算法的基础上给出了艺术画廊 看守问题的启发式算法 得出大部分具有k 个凹点的简单多边形需要的看守数目 g 满足i 坛l g k 的结论 i 二l 2 在正交艺术画廊看守问题中 k a h n k l a w e 和k l e i t m a n 得出了正交艺术 画廊的最小看守数g 上 n 为l n 4 j 本文利用任意正交多边形可进行凸四角剖分的 性质 得到了正交多边形的一个特殊的三角剖分 通过对这种三角形的邻接关系 的分析 运用了一种四染色方案 给出了正交艺术画廊定理一种新的证明 关键词 艺术画廊问题 正交艺术画廊看守 多边形剖分 凹点山形剖分 算法 英文摘要 a bs t r a c t t h ea r tg a l l e r yp r o b l e mo r i g i n sf r o mr e a ll i f e i th a sa t t r a c t e dm o r ea n dm o r e r e s e a r c h e r s n o w a d a y s i th a sv e r yi m p o r t a n ta p p l i c a t i o ni nm a n yd o m a i n s b e c a u s et h e c o m p u t a t i o no fg i sa nn p h a r dp r o b l e m m a n yr e s e a r c h e r st r yt op r e s e n ts o m e n e a r o p t i m a l a l g o r i t h m sf o rt h ea r tg a l l e r yg u a r dp r o b l e m s t h ep a p e rp r o p o s e sa h e u r i s t i ca l g o r i t h mw h i c hs o l v et h en u m b e ro fg u a r d sf o rt h em o s to fp o l y g o n s 析t h kr e f l e xv e r t i c e s i ng e n e r a lc a s e t h en u m b e ri ss u p e r i o rt okg u a r d s t h u s w h e t h e ri n t h e o r yo rp r a c t i c a la p p l i c a t i o n i th a si m p o r t a n c ea n ds i g n i f i c a n c e t h e r ea r et w om a i n l yw o r k si nt h i sp a p e r f i r s t l y t h ea r tg a l l e r yt h e o r e ms h o w st h a tt h em i n i m u mn u m b e ro fg u a r di s j f o rp o l y g o n s c o n c a v ev e a i c e sh a v es p e c i a lr o l ew h e nr e s e a r c ht h en u m b e ro fg u a r d so f p o l y g o n s b e c a u s ekg u a r d si sa r en o to p t i m a lf o rt h em o s to fp o l y g o n sw i t hk r e f l e x v e r t i c e s b a s e do nt h er e f l e xv e r t i c e s t h i sp a p e rp u t sf o r w a r ds u b d i v i s i o na n di t s a l g o r i t h mb ya n a l y z i n gt h es i m p l ep o l y g o n ss u b d i v i s i o na n da l g o r i t h m a n do b t a i n sa c o n c l u s i o nt h en u m b e ro fg u a r d sf o rm o s ts i m p l ep o l y g o nw i t hkr e f l e xv e r t e xi sg w h i c h g 虬 s e c o n d l y i nt h eo r t h o g o n a la r tg a l l e r yp r o b l e mf o rg u a r d k a l l i l k l a w ea n d k l e i t m a np u tf o r w a r dac o n c l u s i o n f o ra r b i t r a r ye v e nn u m b e r s 玎 n 4w eh a v e g 上0 2l n 4 j a c c o r d i n gt ot h ep r o p e r t yt h a ta n yo r t h o g o n a lp o l y g o n i sc o n v e x q u a d r i l a t e r i z a b l e o b t a i n i n gas p e c i a lt r i a n g u l a t i o na b o u to r t h o g o n a lp o l y g o n t h e n a n a l y z i n gt h ea d j a c e n tr e l a t i o nb e t w e e nt h et w oa d j a c e n tt r i a n g l e si nt h et r i a n g u l a t i o n a n du s i n gas o r t4 一c o l o r i n g p r e s e n t i n gan e w p r o o f f o ro r t h o g o n a la r tg a l l e r yt h e o r e m k e yw o r d s t h ea r tg a l l e yp r o b l e m t h eg u a r df o ro r t h o g o n a la r tg a l l e y p o l y g o ns u b d i v i s i o n r e f l e xv e r t e xm o u n t a i ns u b d i v i s i o n a l g o r i t h m 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明 本论文是在导师的指导下 独立进行研究工作所取得的成果 撰写成博 硕士学位论文 仝茎苤画廊羞空间壁的痘蕉式篡洼 除论文中 已经注明引用的内容外 对论文的研究做出重要贡献的个人和集体 均已在文中 以明确方式标明 本论文中不包含任何未加明确注明的其他个人或集体已经公开 发表或未公开发表的成果 本声明的法律责任由本人承担 学位论文作者签名 扭堡璃 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留 使用研究生学 位论文的规定 即 大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版 允许论文被查阅和借阅 本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索 也可采用影印 缩印或扫 描等复制手段保存和汇编学位论文 同意将本学位论文收录到 中国优秀博硕士 学位论文全文数据库 中国学术期刊 光盘版 电子杂志社 中国学位论 文全文数据库 中国科学技术信息研究所 等数据库中 并以电子出版物形式 出版发行和提供信息服务 保密的论文在解密后遵守此规定 本学位论文属于 保密口在 年解密后适用本授权书 不保密匝 请在以上方框内打 论文储繇卞冬帝导师躲渺携 日期 丑 0 7 年6 月弓d 日 一个艺术画廊看守问题的启发式算法 第1 章绪论 1 1 引言 2 0 世纪7 0 年代末 计算几何从算法设计与分析中孕育而生 随着时间的推移 该 学科不断取得辉煌的成果 已成为理论计算机科学中一个新的极有生命力的领域 计算 几何中的研究成果已在计算机图形学 统计分析 模型识别以及其他许多领域中得到了 广泛的应用 艺术画廊问题是计算几何中一个重要的研究方向 在现实生活中具有重要的实际 意义 因此艺术画廊问题一经提出 就受到数学界学者们的广泛关注 随着计算机和 通信技术的发展 以及人们对艺术画廊问题研究的完善 在艺术画廊问题研究过程中所 得到的成果 已经越来越多的应用到人们的实际生活中去 艺术画廊问题最初是由看守 艺术画廊中的绘画作品而被提出来的 目前艺术画廊问题有着广泛的应用空间 如虚拟 现实技术中几何体的碰撞检测 通信网络中天线的 地形 覆盖范围 传感器网络中传 感器的最优布局 各类场所的安全监控等 这些问题都可归结为艺术画廊问题 a r t g a l l e r y p r o b l e m 或其变种 对于艺术画廊问题 计算几何中将艺术画廊抽象为平面简单多边形 而将监视器抽 象为简单多边形中的点 这样就可以把艺术画廊问题抽象为一个平面几何问题 如果这 些点 监视器 能监视到简单多边形中的每一个角落 那么就说这组点 监视器 可以 覆盖整个简单多边形 于是艺术画廊问题就抽象为需要多少个点可以覆盖整个简单多 边形的问题 一般情况下 在计算几何中 将监视器安装在简单多边形的顶点上 将艺 术画廊抽象为一个由若干个 块 组成的平面简单多边形 这样每一个顶点 监视器 都可以将与之相关联的所有 块 都 覆盖 住 于是艺术画廊问题可以抽象为需要多 少顶点可以覆盖整个简单多边形的问题 艺术画廊问题被提出之后 学者们又引出了各种各样的艺术画廊变种问题 在确定 艺术画廊对应的简单多边形所需监视器的数目时 人们希望的是尽量需要少量的监视器 然而 不幸的是学者们已经证明出 求任一简单多边形所需监视器的最少数目 的算法是 第1 章绪论 n p 难的问题 所以人们转向了对简单多边形所需监视器数目的精确界及其相关算法的 研究 1 2 发展现状 1 2 1 多边形的剖分 在计算几何中 通常采用剖分的方法来研究几何体 简单多边形剖分已成为计算几 何的中一个重要研究部分 这种剖分技术不断的被应用到计算机视觉 地球物理 图像 压缩 虚拟现实等越来越多的领域 有着广泛的应用价值 简单多边形是计算几何研究的对象之一 这是由于简单多边形是许多真实物体外形 的一种方便而又精确的描述工具 并且在计算机上很容易实现 然而 简单多边形的形 状可能极为复杂 于是人们就想到可将简单多边形剖分成若干个 小块 即应用多边形 的剖分技术来研究多边形 用来剖分简单多边形的线段通常有两种 一种是对角线 一种是端点在简单多边形 的边界上并位于简单多边形内部的线段 在计算几何中常见的剖分有三角剖分 梯形剖 分 凸边形剖分 单调山形剖分 l 形剖分等 其中三角剖分是最基本的一种剖分技术 它是多边形凸剖分的一种特殊情况 1 2 2 艺术画廊问题 1 9 7 4 年 k l e e 1 1 提出艺术画廊问题 具有刀面墙壁的艺术画廊应该需要多少个监视 器是足够的 而且有的时候是必须的1 2 4 1 9 7 5 年 c h v a t a l 5 第一次证明了这个问题 对 于具有玎面墙壁的艺术画廊 ln 3l 台监视器总是足够的 而且有的时候是必须的 这 一结论被称为艺术画廊定理 6 7 a r tg a l l e r yt h e o r e m 基于m e i s t e r s 的双耳定理 f i s k t 8 于1 9 7 8 年利用多边形三角剖分和染色的方法 给出了艺术画廊定理更为简洁的证明 a v i s t o u s s m n t l 9 1 和c h a z e l l e 0 0 1 分别提出了简单多边形进行三角剖分的算法 此算 法可以在o n l o g n 时间实现 因此 对任意的简单多边形 总可以在o n l o g n 的时间内 在简单多边形中确定in 3i 台监视器的位置 使得简单多边形中任何一点都与其中的至 少一台监视器可见于 l e e a g g a r w a l l l1 1 和l i n 1 2 1 证明了 求任一简单多边形所需监视 一个艺术画廊看守问题的启发式算法 器的最少数目 这一算法是n p 难的问题 1 2 3 其它艺术画廊问题 艺术画廊定理被证明以后 有关艺术画廊问题的相关问题被越来越多的提出 大多 都是对看守者的能力进行限制或是对艺术画廊对应的简单多边形的形状做出不同的限 制 在o r o u r k e 的有关艺术画廊问题的专著f 1 9 里以及在u r r u t i a 2 0 1 的综述里有许多相关 的结论 其中包括要求至少有两台监视器相互可见的联合看守问题 监视器可在边上或 是对角线上移动的看守问题 画廊的墙壁要求垂直的正交艺术画廊看守问题等 1 7 j s 其中正交艺术画廊问题 艺术画廊联合看守问题相对艺术画廊问题及其变种而言更 具有实际意义 因此越来越多的研究者对此问题进行研究 所谓正交艺术画廊看守问题是指画廊对应的简单多边形是一个正交简单多边形 正 交简单多边形就是指多边形的中的每条边都是平行x 轴或y 轴的 也就是说 正交简单 多边形中的每个内角都是9 0 或是2 7 0 k a h n 2 1 证明了对正交艺术画廊看守问题来说 其看守数的上限为ln 4i 通过归纳的方法 h e m a n d e z p e n a l v 铲2 1 证明出关于正交艺术画廊联合看守数的上限 为l n 3 j 所谓艺术画廊联合看守问题是指要求联合看守集合中的监视器不仅要监视好画廊 而且每一个监视器都至少被另一个监视器所监视到 m i c h a e l 和p i n c i u 1 4 1 s 1 证明了联合看守集合的上限应为i3 n l 7i l i a w h u a n g 和 l e e 证明了求联合看守最少数目的问题是n p 难的 1 3 本文的研究内容与安排 本文主要工作安排有 第1 章简单地介绍了艺术画廊问题的实际意义 概括性的论述了艺术画廊问题及 正交艺术画廊看守问题中的一些国内外研究现状 第2 章主要介绍了与本文相关的一些基本的概念 引理等 第2 章简单介绍了艺术画廊问题对应的几种简单多边形的剖分以及用三角剖分和 3 染色方法对艺术画廊看守定理的证明 并在几种简单多边形的剖分基础上提出了一种 第1 章绪论 新的剖分方法一m 形剖分 并在此剖分及其算法的基础上给出了艺术画廊看守问题的启 发式算法 得出大部分具有尼个凹点的简单多边形需要的看守数目g 满足 g j i 的结论 第4 章简单介绍了正交艺术画廊看守问题产生的背景和意义 介绍了正交艺术画 廊看守定理的一种证明方法 在此基础之上利用任意正交多边形可进行凸四角剖分的 性质 得到了正交多边形的一个特殊的三角剖分 运用了一种四染色方案 给出了正交 艺术画廊定理一种新的证明 第5 章对本文的主要研究结果做了总结 并提出了有待解决的问题 一个艺术画廊看守问题的启发式算法 第2 章预备知识 2 1 基本概念 为了更确切地对艺术画廊问题做出定义 必须将画廊的概念作形式化处理 每一个 画廊都是一个三维空间 然而通过它的平面结构图 就可以获得足够的信息来确定监视 器的安放位置 因此 可以利用平面多边形的模型 来表示一个画廊 做出进一步的限 制 要求画廊的模型应是简单多边形 s i m p l ep o l y g o n 所谓简单多边形就是由单个不 自交的 封闭的多边形链所围出的区域 更准确而简洁地说简单多边形就是由一些线段 首尾顺次相接组成的图形 即边之间除顶点外不相交的多边形 这样 在简单多边形中 就不允许出现空洞 一台监视器在画廊中的位置 对应于简单多边形中的一个点 于是 画廊看守问题可以抽象为需要多少个点可以覆盖整个简单多边形的问题 本文把简单 多边形简称为多边形 监视器对应简单多边形中的顶点 定义2 1 嘲 设点x 与点y 是多边形乞内的任意两个点 连接z 和y 如果封闭线段 砂完全位于多边形 内部 那么就说点z 与点少可见 或者是点少与点x 可见 反之 则称点x 与点y 不可见 如图2 1 所示 a 点x 与点y 可见 b 点x 与点j 不可见 a t h ev i s i b l ep a i r so fp o i n t sx a n dy b t h ei n v i s i b l ep a i r so fp o i n t sx a n dy 图2 1 点的可见性 与不可见性 r i g 2 1t h ev i s i b i l i t ya n di n v i s i b i l i t yo fp o i n t s 第2 章预备知识 在研究艺术画廊问题时 一台监视器抽象为多边形中的一个点 由此得出点覆 盖的定义 定义2 2 f 8 如果多边形中每个点与一组监视器中至少一台监视器所在的点可见 那么就称该组监视器覆盖多边形只 也称做该组点 放置监视器的点 覆盖多边形只 定义2 3 3 1 设9 为多边形 中的一个点集 如果对于多边形乞中的任意一点石 石诺9 在9 中一定存在一点w 使x w 相互可见 那么点集9 称为多边形 的一个看 守者集合 简称看守集 设g 乞 是覆盖任意简单多边形只的最小看守数 即 g m i n i s 覆盖p o i 其中s 是 中的一个点集 蚓表示s 中元素的个数 设g 疗 是覆盖任意简单多边形只的最小看守数g 的最大值 即 g n 2 m a x g 以 对具有n 个顶点的任意简单多边形 g 刀 是满足覆盖整个简单多边形的最小看守者数 的最大值 定义2 4 f 3 1 设多边形己中的一个点集蹦足 1 夕是 的一个看守集 2 对于乡宁任一点w 如果存在一点v 夕 并且w 1 使v i v 相互可见 则称够为多边形只的联合看守集 i 漫g g p 是覆盖任意简单多边形 的最小联合看守数 即 昭 m i n i s s 是只的一个联合看守集 l 对任意的整数胛 3 则 g g 玎 2 m a x g g p i p 是一个具有价顶点的简单多边形 因此g g 玎 是覆盖任意简单多边形只的最小联合看守数g g 只 的最大值 一个艺术画廊看守问题的启发式算法 设瓯伽 是覆盖任意正交多边形看守数g 的最大值 即 g 上 刀 m a g 以 i 见是一个具有价顶点的正交多边形 设g g 上魄 是覆盖任意正交简单多边形 的最小联合看守数 即 g g 上 巩 m i n l s s 是正交多边形只的一个联合看守集 l 对任意偶数刀 4 定义 g g l n m 驭 罟 g 上 见 i 见是一个具有价顶点的正交多边形 2 2 艺术画廊问题相关概念与性质 定义2 5 7 设链c 是由多边形边q e j l e j 组成的多边形链 l 是平面上一条直 线 如果与三垂直的的直线z 与c 至多交于一点 即三 n c 或者为空 或者为一个点 则称多边形链c 是关于三是单调的 定义2 6 7 1 如果多边形只的边界犯能分割成两个多边形链c l 和c 2 并且链c 1 c 2 都是关于直线三单调的 那么就说 是关于直线三单调的 此时称只为单调多边形 否 则 就不是单调多边形 如图2 2 所示 本文中用y 轴作为直线三 a 多边形 关于少轴是单调的 b 多边形只关于y 轴不是单调的 a ap o l y g o ni sm o n o t o n ew i t hr e s p e c ty b ap o l y g o ni sn o tm o n o t o n ew i t hr e s p e c ty 图2 2 定义2 6 的示意图 f i g2 2t h es c h e m a t i cd i a g r a mo fd e f t n i t i o n2 6 第2 章预备知识 定义2 7 7 设b 书只 只 l 是见的三个相邻的顶点 并且点只 l 只 的坐标都小于 大 于 或等于只的y 坐标 则称只为岛的岐点 如图2 2 b 所示 点p q m 刀都是 中的岐 占 j 引理2 1 8 1 艺术画廊定理 对于任意的多边形只 只需 在适当位置放置 n 3 j 台监视器 就能保证其中任何一点都可见于至少一台监视器 有的时候 的确需要这么 多台监视器 引理2 2 7 1 如果只是具有后个凹点的任意多边形 设g 是剖分多边形 成凸多边形 的最少数目 那么有 4 l g 可以得到以下结论 明2 1 0 s l 涨 寻 和棚 g g l 眠妒忌忖l 孚j 引理2 11 1 3 2 3 3 1 对带内壁的简单多边形看守集需要最少的看守数目为 r a i n l 2 一3 3 j l 2 m 聆 3 1 l 2 托 m 4 j 引理2 1 2 3 4 1 对带内壁的正交简单多边形中的看守集需要最少的看守数目为 m i n l 刀 2 m 4 j l 船 3 l 拧 2 j m 一2 8 j 第3 章艺术画廊看守问题的启发式算法 第3 章艺术画廊看守问题的启发式算法 1 9 7 3 年 k l e e 提出 具有刀面墙壁的画廊需要多少个看守是足够的 而且有时是必 须的 1 9 7 5 年 c h v a t a l 在文献 6 中证明了具有刀个顶点的简单多边形 所对应的艺术 画廊问题 只需in 3i 台监视器就足够了 而且有时是必须的 1 9 7 8 年 基于m e i s t e r s 的双耳定理 f i s k 给出了艺术画廊定理的更简洁的证明 并证明 任意简单多边形经三 角剖分后 所对应的图均可3 染色 且同一类颜色的点可覆盖整个简单多边形 a v i s 和t o u s s a i n t 已证明 对任意具有 2 个顶点的简单多边形只 总可以在o n l o g n 的时间内确定in 31 个顶点 使得简单多边形中任何一点都至少可见这组顶点中的一个 从而in 3i 顶点足可以覆盖整个多边形 a g g a r w a l l e e 和l i n 证明了 求任一简单多边形所需监视器的最少数目 的算法 是n p 难的 所以 人们转向了对特定的艺术画廊所需最少监视器数精确界及其相关算 法的研究 3 1 多边形的剖分 对于任意一个简单多边形e 在确定覆盖此多边形所需监视器的最小数目时 由于 多边形 的形状可能极为复杂 所以我们似乎很难操作 于是我们就想到可将多边形剖 分成若干个 小块 这样整个多边形就是由若干多个小 块 组成 因为每一 块 都很容易覆盖 若一组点把 中的每个小块都覆盖了 则这组点就可以覆盖整个多边形 所以我们通常应用多边形的剖分技术来研究多边形只 3 1 1 多边形的三角剖分 就具体而言 上面提到的 块 最好就是三角形 因为三角形是最简单的平面多边 形 为了完成这种剖分 在多边形 中添加一些对角线 将某些顶点对连接起来 所谓 的对角线 就是一条丌的线段 它连接于多边形 的某两个顶点之间 而且完全落在只 的内部 通过极大的一组互不相交的对角线 可以将一个多边形剖分为若干多个三角 一个艺术画廊看守问题的启发式算法 形 称之为该多边形的一个三角剖分 由于这一组不相交的对角线集合必须满足最大化 的条件 故可以保证任何三角形各边的内部 都不包含多边形的任何顶点 如果多边形 中存在三个共线的顶点 就可能会出现这种情况 然而 是否每个简单多边形总存在 一个三角剖分呢 由引理2 3 可知任意具有刀个顶点的简单多边形只都存在至少一个三 角剖分 并且每个三角剖分都恰好包含刀一2 个三角形 如图3 1 是一个具有1 3 个顶点 的简单多边形的两种三角剖分 图3 1 a 图3 1 b 图3 1 一个简单多边形的两种三角剖分 f i g3 1as i m p l ep o l y g o na n di t sp o s s i b l et w ot r i a n g u l a t i o n 任意多边形经过三角剖分之后 它就由若干多个小三角形组成 这样对任意的多边 形 给定一个三角剖分 只要在每个三角形中放置一台监视器 狞一2 台监视器就可以实 现对整个多边形的覆盖 实际上由于多边形的顶点可以关联多个三角形 所以把监视器 放在多边形的顶点上可以覆盖更多的区域 1 9 7 8 年 f i s k 利用三角割分技术及3 染色方案给出了艺术画廊定理的证明 现在 用一个例子来说明此定理的证明过程 如图3 2 所示 设只是具有1 4 个顶点的简单多 边形 第3 章艺术画廊看守问题的启发式算法 第一步 用不交叉的对角线把多边形只进行三角剖分 第二步 对多边形e 进行三染色 由引理2 4 可知任意经三角剖分的多边形均可以进行3 一染色 即对顶点赋三种颜色 不妨设为红 蓝 黄 用1 2 3 代表三种不同的颜色 所要求的染色方案必须满足 多边形中的任意边或对角线连接的两个顶点 所染颜色不能相同 称之为 对经过三角 剖分后的多边形的3 染色 三角剖分后的多边形经过如此染色之后 多边形只中每个 三角形的三个顶点必有三种不同的颜色 第三步 把监视器放在染色数目最少的顶点上 从图2 2 中可以看出染蓝色 用2 代表的 的顶点数目是最少的 那就在每个着色 为蓝色的顶点处放置一台监视器 这样每个三角形的顶点上都有一台监视器 显然每个 三角形被它的一个顶点上的监视器所覆盖 从而整个多边形只也都被完全覆盖了 由于 多边形 有 z 个顶点 而且对顶点仅使用三种颜色 由鸽巢原理得 一种颜色仅使用 j 次 因此将使用不多于g 刀 1 j 1 1 j 4 台监视器就可覆盖整个多边形 2 图3 2 多边形三角剖分之后对顶点进行3 一染色 f i g3 23 c o l o r i n gw i t hp o l y g o nt r i a n g u l a t i o n 3 一个艺术画廊看守问题的启发式算法 总之 对于经过三角剖分的任意简单多边形只 都能够对其顶点实施3 染色 于是 只需要不多于ln 3i 台监视器 就可以覆盖任何一个简单多边形 有的时候确实是需要 i n 3i 台监视器的 这样的一个例子就是所谓的 梳状多边形 c o m b s h a p e dp o l y g o n 如图3 3 所示 它有一条长长的水平基边 以及in 31 个分别由两条边形成的 梳齿 任何两个相邻的梳齿之间 由一条水平边相连 只要适当地安排此多边形各顶点的位置 就总能保证一台监视器无论放置在多边形内的什么位置 都不可能同时看到两个梳齿 因此 对于这种情况 不能指望依靠某种策略 每次都找到少于ln 3l 台监视器可以覆 盖住整个简单多边形 换言之 就最坏情况而言 上述监视器数ln 3l 已经是最优的了 图3 3 梳状刀边形需要b 3 j 台监视器 f i g 3 3c o m b s h a p e dp o l y g o nw i t h 刀s i d e sn e e dl n 3 jg u a r d s 三角剖分技术提出之后 许多学者给出了简单多边形三角剖分的算法 其中a v i s 和t o u s s a i n t n 们分别给出对任意多边形 在o n l o g n 时间内进行三角剖分的算法 当多 边形e 为单调多边形时 在线性时间o 内就可以完成三角形的一个三角剖分 3 1 2 多边形的梯形剖分 1 9 8 4 年 c h a z e l l e r 和i n c e r p i 8 1 提出了一种新的剖分方法 梯形剖分 其主要思想 是 通过多边形的每个顶点画水平线 这些水平线与多边形边相交 位于多边形内部的 线段记为s 即sc 并rs n a p 尼 q 其中只是只的顶点 吼是与多边形的交点 第3 章艺术画廊看守问题的启发式算法 卯是多边形只的边界 这一组线段s 将一个多边形剖分为若干多个梯形 称之为该多 边形的梯形剖分 假设多边形只没有两个顶点位于同一条水平线上 图3 4 就是一个 具有1 7 个顶点的多边形进行梯形剖分的例子 分割线有的在顶点的左侧如点l 2 3 4 有的在顶点的右侧如顶点1 4 有的在顶点的两侧 如顶点6 8 1 1 1 2 和1 6 有 的就是顶点本身 如顶点o 5 7 9 1 9 1 3 和1 5 1 9 8 4 年 f o u m i e r 和m o n t u n o 把多边形的梯形剖分作为多边形三角剖分的关键所在 也就是可以通过梯形剖分把多边形瓜分成单调的多边形块 再把此单调多边形进行三角 剖分 如图3 4 就是多边形先进行梯形剖分然后再进行三角剖分的例子 例子中细线的 作用是删去某些点 这些点既是 中的歧点又是 中的凸点 5 7 1 0 1 3 和1 5 从而使 成为单调边形 单调多边形在线性时间o n 内就可以完成一个三角剖分 所 以梯形剖分是多边形进行三角剖分的一个重要过程 1 0 图3 4 多边形进行梯形剖分 f i g3 4at r a p e z o i d a l i z a t i o no f p o l y g o n 只 4 一个艺术画廊看守问题的启发式算法 3 1 3 多边形的凸剖分 多边形凸剖分的主要思想是 在多边形只中添一组对角线或是线段s 即s c 只 并且s n 卯 p 吼 或 乃 q 其中b q i 是多边形见的两个顶点 p j 是多边形 的顶 点 留 与线段j 与多边形 的交点 卯是多边形乞 的边界 通过这组对角线或是线段 把多边形剖分成若干多个 小块 使得每一个 小块 都是一个小凸多边形 从而把 多边形只分割成若干多个凸 块 通过多边形凸剖分的定义我们可以得出多边形的三 角剖分是一个特殊的凸剖分 1 9 8 3 年 h e r t e l 和m e h l h o r n i s 提出了利用对角线进行凸剖分的方法 首先对多边形 进行三角剖分 然后保留每个顶点必要的对角线d 移掉每一个顶点中不必要的对角 线 这样就完成了多边形的凸剖分 其中必要的对角线d 是指如果删除对角线d 就会使 与d 关联的顶点产生非凸的顶点1 也就是说如果d 是必要的对角线 那么d 一定关联 着顶点v 并且顶点 一定是一个凹点 如图3 5 a 所示 对角线d 就是必要对角线 其它称为非必要对角线 图3 5 中的 b 至 c 图就是通过利用删除非必要对角线进行凸剖 分的例子 a b 图3 5 利用对角线进行多边形的凸剖分 f i g3 5p o l y g o n sc o n v e x s u b d i v i t i o nw i t hd i a g o n a l s c 多边形凸剖分的最终目的是把多边形分成若干多个小凸块 而实现这一目的的关键 就是使多边形中的凹点在新的凸块中不在是凹点 下面介绍多边形凸剖分的另一种方 第3 章艺术丽廊看守问题的启发式算法 法 此方法的主要思想是 在多边形的每个凹点对应的角处画一条角平分线至多边形 只的边界或顶点或是已有的角平分线上 这些角平分线将一个多边形剖分为若干多凸多 边形 这样 整个多边形就是由若干多个凸多边形组成 图3 5 就是一个具有5 个凹点 1 2 个顶点的多边形凸剖分的例子 本例是从凹点r 1 开始进行剖分的 在凹点乃处画角平 分线时 此角平分线交在凹点吒的角平分线上 在凹点 处画角平分线交在多边形的顶 点上 经过凸剖分把整个多边形分成5 个凸多边形 在每个凸多边形的一个顶点处放置 一台监视器 每个凸多边形就被覆盖了 从而整个多边形也就完全被覆盖了 图3 6 多边形的每个凹点对应的角处画一条角平分线进行凸多边形剖分 f i g3 6p o l y g o no fc o n v e xp d r t i t i o nw i t ha n g u l a rb i s e c t o rc o m ef r o me v e r yr e f l e xv e r t e x i np o l y g o n 由上面多边形剖分的例子可知剖分多边形的线段通常有两种 一种是多边形的对 角线 一种是端点在多边形的顶点和边界上并位于多边形内部的线段 上面提到的凸多 边形剖分是通过利用画出每个凹点对应的角平分线来完成的 其中画出每个凹点对应的 角平分线最终的目的是破坏多边形中的凹点 使多边形只的凹点在新的多边形中已不在 是凹点 最终把多边形 分成若干多个 j d j 多边形 一个艺术画廊看守问题的启发式算法 对于任意的具有k 个凹点的多边形 进行凸剖分之后 凸边形的数目与凹点的数 目有什么关系呢 由引理2 2 可知 如果乞是具有七个凹点的任意多边形 设g 是剖分 多边形只成凸多边形的最少数目 那么有i l 1 g 七 1 此引理用上面所提到的剖 分即可证明 如图3 7 a 所示 在多边形只的每个凹点对应的角处画一条角平分线 因 而得到一个凸剖分 其凸多边形的数目为 1 另外 一条对角线至多可以分解两个凹 点 这便产生l i 1 个凸多边形 如图3 7 b 所示 a 1 个凸多边形 b f 1 1 个凸多边形 a t h en 哪b e r0 f c n v e xp o l y g o n si s 1 b t h en u m b e r f c o n v e xp l y g o n si sr 卜l 图3 7 凸多边形的个数 f i g3 7t h en u m b e ro fc o n v e xp o l y g o n s 对于任意的具有七个凹点的多边形只 它至多需要多少台监视器呢 引理3 1 2 0 如果对于具有七个凹点的任意多边形 那么至多需要后台监视器即 可看守整个多边形 有的时候确实需要这么多监视器 由引理2 2 可知 具有 个凹点的多边形 进行凸剖分至多可以被瓜分成r 1 个凸 多边形 所以这样就把多边形只分解成 1 个凸多边形 每个凸形都至少包含只中的一 第3 章艺术画廊看守问题的启发式算法 个凹点 把监视器放到每个凹点处 这样每个凸多边形被覆盖了 从而整个简单多边形 也被完全覆盖了 有的时候对于一些特殊的多边形 台监视器是必须的 如图3 8 所示 对于这 种情况 不能指望依靠某种策略 每次都找到少于k 台监视器 换言之 此种情况k 台 监视器已经是最优的了 a 图3 8 这些多边形确实需要 个监视器 f i g3 8p o l y g o n sn e e d g u a r d s c 有的时候把多边形进行凸剖分之后 在每个小凸多边形中的原多边形中的凹点处可 以不用放置监视器 如图3 7 a 所示 2 台监视器就可以覆盖整个多边形了 所以对于 具有k 个凹点的任意多边形只至多需要k 台监视器即可看守整个多边形 这里的k 台是 个上限 如果能够为特定的某个多边形找到其所需监视器的最小数目 而不是一个笼统 的最坏上限 那自然是再好不过的了 但不幸的是 计算出特定多边形所需监视器的 最小数目 这一问题 是n p 难的 尽管如此 我们试着给出一些求最小监视器数目的 启发式算法 3 2 艺术画廊看守问题的启发式算法 由艺术画廊定理我们知道对于任意的多边形 in 3i 台监视器足可以覆盖整个简 单多边形 在研究多边形所需监视器的数目中 多边形中的凹点起着非常重要的作 用 这是因为在多边形中每出现一个凹点就会引起一些不可见点对出现 所以在一般情 一个艺术画廊看守问题的启发式算法 况下 凹点相对于凸点覆盖的范围更大一些 由引理3 1 可知 对于具有k 个凹点的任 意多边形只 至多需要k 台监视器即可看守整个多边形 显然当多边形e 中凹点数 忌 l j 时 若把监视器放在这后个凹点处 结果相对于l j 是比较优的 另 方面对 于具有后个凹点的多边形 来说 在一般情形下 台监视器不是必须的 如图3 1 0 所 示 a 图3 9 只需一台监视器可以覆盖整个多边形 f i g3 9o n l yo n eg u a r dc a ng u a r dt h ep o l y g o n 类似于这样的多边形还有很多 后台监视器只是它们所需看守数的一个上限 那么 具有七个凹点的多边形 所需看守数目的最少数目是多少呢 我们知道a g g a r w a l n 2 1 l e e 和l i n n 羽证明了 求任一简单多边形所需监视器的最少数目 的算法是n p 难的 但 是我们能不能进行某些操作使得任一具有 个凹点的简单多边形所需的监视器数相对 比较优呢 出于这点考虑 本文给出了求艺术画廊所需数目监视器数的一个启发式算 法 3 2 1 多边形m 形剖分及其算法 前面介绍了多边形的凸边形剖分 三角剖分 梯形剖分都是特殊的凸边形剖分 其实在多边形中也存在其它类型的剖分 比如多边形的单调山形剖分 正交多边形中l 形剖分等 由于在研究艺术画廊所需监视器的数目中 多边形中的凹点起着特殊的作 用 所以本文从凹点的角度给出多边形的一种新的剖分方法一m 形剖分 第3 章艺术画廊看守问题的启发式算法 定义3 1 在 中选一凹点 按顺时针方向连接与它可见的第二个凹点r 此连线 把只分成两个简单多边形 这两个简单多边形称做凹点山形 连接这两个凹点的连线称 做基线 与基线连接的两个凹点称做基凹点 定义3 2 若在凹点山形多边形中除了两个基凹点之外 凹点山形中只有一个凹点 则称此凹点山形为m 形多边形 不是基凹点的那个凹点称做中间凹点 定义3 3 通过极大的一组互不相交的基线 可以将一个多边形e 剖分为若干多个m 形多边形和若干个尸 多边形 称之为该多边形的一个m 形剖分 其中尸7 是多边形中除 了m 形多边形外剩余的多边形 图3 1 0 就是一个m 形剖分的例子 基线 吩 吩吩把多边形分成了三个部分p g 9 2 其中p g 是m 形多边形 9 2 是以中除了m 形多边形之外的多边形见 即9 2 p 图3 1 0m 形剖分 f i g3 10m s u b d i v i s i o n 现在给出多边形 进行m 形剖分的算法 见算法3 1 其中形代表凹点山形 二全茎查耍堕墨室塑垦塑旦垄壅簦鲨 p 一 一 算法3 1 多边形的凹点m 形剖分 预处理确定多边形 的凹顶点 并对凹点按照顺时针进行排号 设为 r 吒 吃 r j i l 2 七 输入 多边形 的顶点魏 而 m 仍 而 儿 见 以 顺时针方向排 列 输出m 形序列帆及其顶点序列 a 1 a 2 r m p 2 1 耽2 气 见l p 2 2 i 步1 i 1 m 1 步2在多边形 中以凹点i 为起点按顺时针方向寻找与它可见的第二 个凹点 步3如果 不存在 以 为起点重复步2 否则连接 0 如果w 中有一个凹点 即w 为m 形 输出坂 进行步4 否则以 为起点重复步2 步4以 为起点重复步2 直至多边形见被分割完毕 给出多边形m 形剖分及其算法之后 我们不禁会问 是不是任意的多边形都存在m 形剖分剖分呢 如果存在进行m 形剖分之后m 形多边形的个数又是如何呢 现聋这个 问题 定理3 1 若 是具有后 k 3 个凹点的多边形 设g 是剖分多边形 成m 形 多边形的最少数目 则有 g l 等j 证明 1 在多边形 中 以一凹点为起点按照算法3 1 进行m 形剖分时 每 个凹点山形都不是m 形多边形 如图3 1 2 口 所示 在此多边形中 不妨以凹点d 为 第3 章艺术画廊看守问题的启发式算法 起点进行m 形剖分 这样就把此多边形分成两个凹点山形多边形 每个凹点山形都不 是m 形多边形 也就是说这种类型的多边形不存在m 形剖分 m 的最小数是0 即 g 0 2 在多边形 中 以一凹点为起点按照算法3 1 进行m 形剖分时 每一个凹点 山形都是m 形多边形 如图3 1 2 b 所示 在此多边形中 以凹点a 为起点进行m 形剖 分 每一个凹点山形都是m 形多边形 这种类型的多边形可以产生1 孚 j 个m 形多边 形 即g l 孚 j 所以此定理成立 a b 图3 11 定理3 1 证明示意图 f i g3 11t h es c h e m a t i cd i a g r a mo f t h e o r e m3 1 3 2 2 看守数目的启发式算法 由前面的定义3 4 可以知道 肘形多边形中有一条基线 这条基线关联着两个凹点 除了这两个凹点之外 m 形多边形中还有一个中间凹点 此凹点可能出现以下几种情 况 定义3 4 在m 形多边形中 如果与中间凹点关联的两个顶点至少能找到一个基凹 点与之可见 那么就称此中问凹点为不必要凹点 如图3 1 2 所示 一个艺术画廊看守问题的启发式算法 图3 1 2 肘形多边形中的不必要凹点 f i g3 12u n n e c e s s a r yr e f l e xv e r t e xi nmp o l y g o n 定义3 5 在m 形多边形中 如果与中间凹点关联的两个顶点中有一个不能找到一 个基凹点与之可见 那么称此中间凹点为必要凹点 如图3 1 3 所示 图3 1 3 必形多边形中的不必要凹点 f i g3 13n e c e s s a r y r e f l e xv e r t e xi nm p o l y g o n 根据前面的两个定义 可以如下得到两个结论 定理3 2 在m 形多边形中 如果中间凹点为不必要凹点 那么m 形中的两个基凹 点可以覆盖整个m 形多边形 证明 在m 形多边形中 设基凹点为 巧 中间凹点为v 与之关联的两个顶点为 1 1 一 因为中间凹点1 是不必要凹点 所以与之关联的两个顶点v 一至少能找到一个 基凹点与之可见 如图3 1 4 所示 连接 v 一 疋 这两条连线把m 形多边形分成了三 部分 由于第一部分和第三部分都是由一个基凹点 有可能是两个 和m 形多边形中的 第3 章艺术画廊看守问题的启发式算法 若干个凸点组成的