（应用数学专业论文）艺术画廊4染色及联合看守问题研究.pdf

中文摘要 摘要 艺术画廊问题来源于实际生活，与简单多边形三角剖分是密不可分的，多年 来，已经引起越来越多的研究者的关注现如今，它在现实生活许多领域中都有着 重要的应用因为艺术画廊4 染色方法可以减少大部分简单多边形需要的看守数 目，因此，无论在理论上还是在实际应用中，对其研究都具有重要的意义 本文主要在3 染色的基础上研究艺术画廊4 染色问题，以及联合看守问题中 一类特殊简单多边形的联合看守上限问题 首先，在艺术画廊看守问题中，因为对绝大多数的简单多边形来说，由3 - 染 色方法得到的结果并不是最优的所以，本文根据三角剖分与二叉树的对应关系， 通过分析三角剖分中两相邻三角形的邻接关系，利用染色的方法，提出4 - 染色方 法以及4 染色规则，并对4 染色后的情况进行了分析与说明得出任一类颜色的点 覆盖整个简单多边形的条件、至少一类颜色的点覆盖整个简单多边形的条件，以 及对不能覆盖产生的原因进行分析 其次，在联合看守问题中，m i c h a e l 得出了联合看守集合的上限应为f3 n 一1 71 本文通过对m i c h a e l 证明过程以及相关结论的分析，首先将一个三角剖分乃划分为 两个三角剖分瓦，+ ：和乏其中朋 6 ，7 ，8 ，9 ) ，然后对三角剖分乙进行分析，最 后利用归纳法，对一类特殊的简单多边形，即简单多边形三角剖分的对偶图为链 状的情况，证明了联合看守集合至少需要i2 n 51 个联合看守 关键词：简单多边形；三角剖分：艺术画廊定理；4 - 染色；联合看守 英文摘要 4 - c o l o r i n go ft h ea r tg a l l e r ya n d as p e c i a la r tg a l l e r yf o rg u a r d e d g u a r d s a b s t r a c t t h ea r tg a l l e r yp r o b l e mi so r i g i nf r o mt h er e a lw o r l d ，a n di sc l o s e l yr e l a t e dt ot h e t r i a n g u l a t i o no ft h ep o l y g o n f o rm a n yy e a r s ，i th a sa t t r a c t e dm o r ea n dm o r er 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 em e t h o do f 4 - c o l o r i n gf o ra r tg a l l e r y c a nr e d u c et 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 n , t h e r e f o r e ，w h e t h e ri nt h e o r yo r i nt h ep r a c t i c a la p p l i c a t i o n , i ti so f g r e a ts i g n i f i c a n c e o nt h eb a s i so f3 - c o l o r i n g , t h ep r o b l e mo f4 - c o l o r i n gf o ra r tg a l l e r ya n dt h e m i n i m u mn u m b e ro fg u a r d e dg u a r d si nas p e c i a lk i n do fs i m p l ep o l y g o na l e i n v e s t i g a t e d f i r s t l y , i na r tg a l l e r yp r o b l e mf o rg u a r d ，b e c a u s e , t h er e s u l t so b t a i n e df r o mt h e m e t h o do f3 - c o l o r i n gi sn o to p t i m a lf o rm o s ts i m p l ep o l y g o n t h e r e f o r e ，a c c o r d i n gt o t h ec o r r e s p o n d i n gr e l a t i o nb e t w e e nt h et r i a n g u l a t i o na n dt h eb i n a r yt r e e b ya n a l y z i n g t 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 , u s i n gt h e m e t h o do fc o l o r i n g , t h em e t h o do f4 - c o l o r i n ga n dt h er u l e so f4 - c o l o r i n gi sp r o p o s e d ， a n dt h ep r o b l e mh a sb e e nd e s c r i b e da n da n a l y z e da f t e r4 - c o l o r i n g a l s ot h ec o n d i t i o no f t h ee v e r yc o l o rc a l lc o v e rt h ew h o l ep o l y g o ni so b t a i n e d ，a n da tl e a s to n ec o l o rc a n c o v e rt h ew h o l ep o l y g o ni so b t a i n e d t h e na n a l y z et h er e a s o nw h yt h ep o i n t sw i t ht h e s a m ec o l o rc a n tc o v e rt h ew h o l ep o l y g o n s e c o n d l y , i na r tg a l l e r yp r o b l e mf o rg u a r d e dg u a r d s ，m i c h a e le s t a b l i s h e dat i g h t b o u n df o rg u a r d e dg u a r d s ：【- 3 n 一1 7 j i nt h i sp a p e r , b a s e do nt h ea n a l y s i so ft h e m i c h a e l sp r o v ea n dt h er e l e v a n tc o n c l u s i o n s ，f i r s t , d e c o m p o s e st h et r i a n g u l a t i o nz i n t o 乙州2a n d 瓦，w h e r eme 6 ，7 ，8 9 ) ，a n dt h e na n a l y z et h et r i a n g u l a t i o n 乙 f i n a l l y , b yu s i n gt h ei n d u c t i v em e t h o d ，p r o v e 【- 2 n 5 jg u a r d e dg u a r d sa l w a y se n o u g h f o ras p e c i a lk i n d o fs i m p l ep o l y g o n - - t h et r i a n g u l a t i o n si s o m o r p h i cg r a p hi s c a t e n a r i a n 英文摘要 k e yw o r d s ：s i m p l ep o l y g o n ；t r i a n g u l a t i o n ；a r tg a l l e yt h e o r e m ；4 - c o l o r i n g ；g u a r d e d g u a r d s 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 7 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博士硕士学位论文 竺苎盔画盛垒：染色厘珐金蚕室间题班究：。除 论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已 经公开发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：年月日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法 ，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 。扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密口( 请在以上方框内打“ ) 论文作者签名：导师签名： 日期：年月日 艺术画廊4 染色及联合看守问题研究 第1 章绪论 1 1 引言 计算几何是数学与计算机科学的一个重要分支自2 0 世纪7 0 年代末，计算 几何从算法设计与分析中孕育而生在不到3 0 年时问里，该学科已经有了巨大的 发展，不仅产生了一系列重要的理论成果，也在众多实际领域中得到了广泛的应 用 三角剖分作为计算几何一个重要的方面，应用十分广泛，多年来一直在有限 元分析、计算流体力学、地球物理、科学计算可视化工程等应用领域发挥着及其 重要作用 艺术画廊看守问题是计算几何的一个重要研究方向在现实生活中具有重要 的实际意义，因此艺术画廊看守问题一经提出，就受到全世界数学界的广泛关注 近年来，吸引着越来越多的人对其进行研究，将成为今后相当时期的研究重点并 有着广阔的前景和极强的生命力人们在对艺术画廊看守问题进行的研究过程中 所创造的新的思想、方法和技巧也为后人的研究提供了一个又一个坚实的基础 也为今后的研究开辟了更为广阔的空间 随着现代社会科学技术的高速发展，以及艺术画廊看守问题研究的不断完善， 在艺术画廊看守问题研究过程中所得到的结论将会更为广泛的应用到人民群众的 实际生活中去 艺术画廊看守问题最初是由看守艺术画廊中的绘画作品而被提出来的，目前 艺术画廊定理有广泛的应用空间，因为不仅仅是艺术画廊中出自名家手笔的绘画 作品需要看守，各个商场、超市、银行等等场所，也都需要看守对于这些场所 的看守，仅仅依靠人去看守是不可能的随着科技的发展，可以应用先进的设备 对上述场所进行看管，例如监视器在一般情况下，这些监视器都被挂在天花板 上，绕着某个垂直的轴旋转然后由监视器所采集到的图像，传送到看守室的电 视屏幕上这样，就可以节省大量的人力资源，显然，对于在看守室电视屏幕前 面的看守员来说，所需要关注的屏幕越少越好也就是说，要尽可能地减少监视器 第1 章绪论 的数目，监视器数目少也可以使相应的保安系统成本更低但是，监视器数目也 不可能过少，因为画廊、银行、商场等场所都存在必须看守的地方，因此这些需 要看守的地方都必须落在至少一台监视器的视野之内所以对监视器的安装位置 有很高的要求最后的目标是：使每台监视器都能在需要看守的区域照应到更大 的范围这就是通常所谓的艺术画廊问题( a r tg a l l e r yp r o b l e m ) 在学者们研究艺术画廊看守问题的过程中，又引出了形形色色的艺术画廊变 种问题【9 】，例如要求至少有两台监视器相互可见、监视器可在边上移动的边覆盖、 监视器可在对角线上移动的对角线覆盖、去除一个看守而其他看守都可以知道的 合作看守、画廊的墙壁要求垂直等相关的问题【i l - 1 3 1 艺术画廊问题及其变种问题看似简单，只需要在看守区域中特定的位置安放 几个必要的监视器但实际上，对任意的区域来说，要知道需要监视器的最少数 目以及具体的安放位置，就需要确定的安放监视器的方法，这就需要广大学者对 其进行更加深入的探索与研究 1 2 发展现状 1 2 1 计算几何与三角剖分发展现状 如今，计算几何不仅拥有自己的学术刊物和学术会议，而且形成了一个由众 多活跃的研究人员组成的学术群体，因此已经成长为一个被广泛认同的学科该 领域作为一个研究学科之所以会取得成功，一方面是由于其涉及的问题及其解答 本身所具有的美感，另一方面，也是由于在众多应用领域( 诸如计算机图形学、 地理信息系统和机器人学等) 中，几何算法都发挥了重要的作用 剖分研究的是将给定空间离散为简单几何体集合的方法最早源于二十世纪 五、六十年代的有限元分析早期剖分主要是人工剖分，至今已有五十多年的研究 历史早期剖分主要是矩形、正六面体剖分，矩形剖分的局限性大，只能使用于几 何体简单规则的情况为了增加灵活性，发展为四边形、六面体网格尽管四边形 网格比较灵活，但仍然无法剖分许多复杂的形体因此，七十年代末，八十年代初， 开如研究以三角形、四面体为单元的剖分技术，即三角剖分技术近年来，三角剖 艺术画廊4 染色及联合看守问题研究 分技术不断被应用到计算机视觉、模式识别、图像压缩、虚拟现实等越来越多的 领域 多边形简单的说就是在同一平面内，由些线段首尾顺次相接组成的图形多 边形是计算几何研究的对象之一，这是由于多边形是许多真实物体外形的一种方 便而又精确的描述工具，并且在计算机上很容易实现然而，多边形又可能是相当 复杂的对象，因此经常需要把它们看作由更简单的部分组成，这就需要对多边形 进行剖分 由于三角形是最简单的一个平面图形，所以，在计算几何、计算机图形学、曲 面逼近、科学计算可视化等领域都有广泛的应用简单多边形区域可以看成是由许 多三角形拼凑而成，对简单多边形区域的研究往往可以转化为对三角形的研究，或 对其对偶图形的研究 1 2 2 艺术画廊问题的发展和现状 艺术画廊问题是由k l e e 与c h v a t a l i 】在1 9 7 4 年提出的：具有以面墙壁的画廊 需要多少个看守是足够的，而且有时是必须的【3 5 】1 9 7 8 年，c h v a t a l 第一次证明： 对于具有n 面墙壁的画廊，ln 3i 台监视器总是足够的，而且有时是必须的这一 结论被称为艺术画廊定理( a r tg a l l e r yt h e o l a i i ) ，或者看守者定理( w a t c h m a n t h e o r e m ) ( “包含刀个顶点的任何简单多边形，只需( 放置在适当位置的) in 3i 台监视器，就能保证其中任何一点都可见于至少一台监视器有的时候，的确需要 这么多台监视器【2 别 ) 基于m e i s t e r s 的双耳定理( t w oc a r st h e o r e m ) ，f i s k 4 1 利 用三角剖分技术和染色的方法，给出了艺术画廊定理的更为简洁的证明，由此可 轻松地导出“任意简单多边形经三角剖分后，所对应的图均可3 染色”这一结论， 且同一类颜色的点可覆盖整个简单多边形a g g a r w a l 习以及l e e 和l 甜6 1 证明了“求 任一简单多边形所需看守的最少数目”这一算法问题是n p 难的 a v i s 和t o u s s a i n t 7 1 以及c h a z e l l e 8 】分别给出了可以在伙甩l o 鲈) 时间内对简单多 边形进行三角剖分的不同算法由此，对任给一个包含n 个顶点的简单多边形，总 第1 章绪论 可以在o ( n l o g n ) 的时间内，在简单多边形中确定i n 3l 台监视器的位置，使得简单 多边形中任何一点都可见到其中的至少一台监视器 1 2 3 艺术画廊问题中联合看守发展和现状 自从c h v a t a l 证明艺术画廊定理以后，越来越多有关艺术画廊看守的相关问题 被提出，其中联合看守问题相对艺术画廊而言更具实际意义，由此吸引了越来越 多的研究者的关注 联合看守问题和合作看守问题是两个相关的问题，其中联合看守是要求联合 看守集合中的看守不仅要看护好艺术画廊，而且每一个看守都至少被另一个看守 所看到，即联合看守的集合中不存在孤立点而合作看守是指如果有一个看守出事 了，那么其它所有的看守都要知道即合作看守集合中的点，可以在多边形的内部 由多边形对角线形成一条链 合作看守定理是由l i a w 掣1 3 1 在1 9 9 3 年第一次提出来的，并证明了计算任一 简单多边形的合作看守数目是n p 难的1 9 9 2 年，a h l f e l d 和h e c k c r 确定了多边形 的最小连接数的问题【3 2 】对于缸螺线多边形来说，合作看守数目为m 【3 3 1 1 9 9 4 年， h e r n a n d e z p e n a l v e r 【1 6 】对要求一台监视器至少与另一台监视器可见的联合看守问题 给出的联合看守集合上限是i 2 n 5i ；m i c h a e l 和p i n c i u 1 4 ，b 1 推翻了 h e r n a n d e z p e n a l v c r 关于联合看守集合的上限为i2 n 5i 的结论，证明了联合看守集 合的上限应为i 3 n 一1 71 z y l i n s k i t 1 证明了对于单调多边形和螺线多边形来说，联 合看守集合的上限为i 2 n 5l ，对于星状多边形来说，i3 n 一1 71 个联合看守是必需 的 l i a w ，h u a n g 和l e e 2 9 1 证明了求合作看守最少数目的问题是n p 难的 1 2 4 其它艺术画廊问题发展与现状 由艺术画廊问题出发，引出了形形色色的变种问题【i s , 1 9 其中包括要求至少有 两台监视器相互可见的看守问题、监视器可在边上移动的看守问题、监视器可在 对角线上移动的看守问题、去除一个看守而其他看守都可以知道的看守问题、画 艺术画廊禾染色及联合看守问题研究 廊的墙壁要求垂直的看守问题等在计算几何中，把画廊抽象为简单多边形，把一 台监视器抽象为简单多边形中的一个点，那么可以把艺术画廊问题抽象为一个平 面几何问题画廊看守问题就可以抽象为需要多少点可以覆盖整个简单多边形 同样其变种问题可以抽象为联合看守、边覆盖、对角线覆盖、合作看守、正交画 廊看守、移动看守、有限视角的看守、有限视角的移动看守、正交多边形的移动 看守等等问题【2 0 。2 2 1 在o r o u r k e 的有关画廊看守的专著罩以及在u r r u t i a t 2 8 】的综 述里有许多相关的结论 t o u s s a i n t 7 1 给出了对任意简单多边形来说边覆盖的上限为in 4l ，而后 0 r o u r k e 给出了边覆盖的上限应为in 5i ，1 9 9 1 年s u b r a m a n i y a m 和d i w a n 8 】说明 了当n = 1 4 时，上限为in 5i 也是不正确的 h e m a n d e z p e n a l v e r 3 4 】通过归纳的方法得出了关于正交多边形的联合看守数的 上限为【n 3 j k a h n 2 3 1 证明了对正交多边形来说，其看守数的上限为l 行4i 对于任意的简单多边形，如果简单多边形中有册对连接起来的对角线，称 这样的问题为带内壁的简单多边形艺术画廊看守问题【1 2 】1 9 9 9 年，k u n d g e n 在文献 【2 4 】中给出了带内壁的简单多边形看守集需要最少的看守数2 0 0 1 年，h l i n e n y 在文 献 2 5 中完善了k u n d g e n 的证明h u t c h i n s o n 在文献 2 6 】中给出了在正交简单多边 形中的看守集需要最少的看守数 研究带有视角的看守者问题，也是目前许多学者的研究方向【4 2 小】例如看守者 具有1 8 0 度的可视角度【3 9 删或具有可变的可视角度在1 9 9 7 年，u r r u t i a 3 8 1 提出了看 守者带有1 8 0 。视角的艺术画廊看守问题，在2 0 0 0 年，c s a b a 3 7 】给出了相关的证明 t o t h 4 1 1 给出了带有统一视角的看守者集的上限 1 3 本文的研究内容与安排 艺术画廊问题有着重要的实际应用价值，多年来一直是计算几何中一个很活 跃的课题从事这一领域研究的人越来越多，研究范围也日趋广泛，理论成果也是 第1 章绪论 日臻丰富与完善以此为背景，本文就艺术画廊看守者顶点4 染色及艺术画廊联合 看守问题做进一步的研究主要工作安排有： 第1 章是绪论，概括性地介绍了艺术画廊问题的研究背景，并讨论了研究艺 术画廊看守问题的实际意义，简单介绍了论文所需的一些相关知识，给出艺术画 廊看守及联合看守中的一些国内外研究现状 第2 章是基本概念、引理及预备知识，主要介绍了在本文中使用的与艺术画 廊看守问题相关的一些基本的概念i 引理等，并对一些在本文中出现的符号做出 简单的说明 第3 章介绍了艺术画廊看守问题产生的背景和意义，给出了艺术画廊看守定 理以及艺术画廊看守问题中的顶点3 一染色并在3 一染色的基础上提出一种新的染 色方法，在文中给出4 一染色规则与4 一染色方案，并给出相关的一些主要结论 第4 章简单介绍了艺术画廊联合看守问题产生的背景和意义，介绍了艺术画 廊联合看守集合的上限联合看守定理及相关的研究成果并根据联合看守定理的 证明思想，得出当简单多边形三角剖分的对偶图为链状时，联合看守集合的上限 为i2 n 5i ，并给出完整的证明及相关的一些主要结论 第5 章是结束语，主要总结了本文所作的主要工作，并提出了有待解决的问 题 艺术画廊4 _ 染色及联合看守问题研究 2 1 基本概念与记号 第2 章预备知识 为了更确切地对艺术画廊问题做出定义，首先必须将画廊的概念作形式化处 理自然地，每一个画廊都是一个三维空间，然而通过它的平面结构图，就可以获 得足够的信息来确定监视器的安放位置因此，可以利用平面多边形的模型，来表 示一个画廊做出进一步的限制，要求画廊的模型应是简单多边形( s i m p l e p o l y g o n ) ，更准确而简洁地说，简单多边形的边界是一条j o r d a n 曲线，即由单个 不自交的、封闭的多边形链所围出的区域，这样，就不允许出现空洞一台监视器 在画廊中的位置，对应于多边形中的一个点于是画廊看守问题可以抽象为需要多 少点可以覆盖整个简单多边形 由此，在计算几何中，艺术画廊问题可以描述为包含 个顶点的任意简单多边 形，只需在适当位置选取ln 31 个顶点，就能保证简单多边形中任何一点都可见于 in 31 个点中的至少一个 记号： 只 具有n 个顶点的平面简单多边形 z 具有n 个顶点的简单多边形三角剖分 q 具有力个顶点的简单多边形四角剖分 g 具有n 个项点的三角剖分或者是一个四角剖分 r 看守者集合 p 联合看守者集合 g ( n ) 最小看守数 g g ( n ) 最小联合看守数 g ( )简单多边形的最小看守集合 g g ( p 。) 简单多边形的最小联合看守集合 第2 章预备知识 如果说只内的点x 与y 相互可见，那么线段x y 完全位于只内部( 只中的任意 点都可见于其本身) 如果把点集i 称为看守者集合，那么对于e 中的任一点x ， 在r 中一定存在一点w ，使五w 相互可见 在个简单多边形中，用一组互不相交的对角线将其分解为多个三角形， 称之为该多边形的一个三角剖分， 如果g ( 只) 是只的最小看守集合，对任意的整数n 3 ，定义： g ( n ) = m a x l g ( p 。) l ：只是包含以个顶点的简单多边形) 对具有力个顶点的任意简单多边形，g ( n ) 是满足覆盖整个简单多边形的最小 看守者数 设只中的一个点集p 满足： ( 1 ) 对中的任一点x ，在r 中存在一点w ，使w 可见于工，其中r 是只的一 个看守者集； ( 2 ) 对任一点w ，存在一点，属于r ，并且w 不等于v ，使，w 相互可见 则称p 为的联合看守集。 设g g ( p 。) 是的最小联合看守集合，对任意的整数行3 ，定义： g g ( n ) = m 觚日昭( 只) i ：是包含九个顶点的简单多边形 对具有万个顶点的任意简单多边形，g g ( n ) 是满足覆盖整个简单多边形的最小 联合看守数 2 2 艺术画廊问题相关概念与性质 本文将用到了图论以及计算几何中一些基本的概念、定理，此处不加说明地 列举如下： 定义2 1 【2 1 在一个简单多边形中，用一组互不相交的对角线将其分解为多个三 角形，称之为该多边形的一个三角剖分，简记为z 设是简单多边形只的一个三角剖分，则相应的最小看守集合与联合看守集 合分别记为g ( ) 与g g ( r ) 艺术画廊4 - 染色及联合看守问题研究 引理2 1 【1 1 ( 艺术画廊定理) 包含刀个顶点的任何简单多边形，只需( 放置在 适当位置的) in 3i 台监视器，就能保证其中任何一点都可见于至少一台监视器 有的时候，的确需要这么多台监视器 引理2 2 e 2 】任何简单多边形都存在至少一个三角剖分；若其顶点数目为，z ，则 它的每个三角剖分都恰好包含万一2 个三角形 引理2 3 【2 1 任给一个包含刀个顶点的简单多边形，总可以在0 ( ，l l o g 门) 的时 间内，在中确定3 j 台监视器的位置，使得只中的任何一点都可见到其中至少 一台监视器 c h v a t a l 证明艺术画廊定理以后，随着艺术画廊问题研究的深入，艺术画廊联 合看守问题也得到了广泛的关注，与其相关的研究成果也不断出现艺术画廊联合 看守问题也由于其现实意义得到了越来越多的关注 2 3 几种典型的艺术画廊看守问题 艺术画廊问题提出以后，各种各样形形色色的问题被提出，例如，对区域( 画 廊) 做出不同的限制，或者对看守者的能力进行限制例如对j 下交多边形来说，每 一个内角都是9 0 。或2 7 0 。，即两相交的边是垂直和水平的对任何一个正交多 边形来说，它都有偶数条边 如果艺术画廊是一个正交多边形，那么k a h n ，k l a w e 和k l e i t m a n 给出了如下 的结论： 引理2 4 【3 0 】( 正交艺术画廊定理) 对任意的刀4 ，则具有刀个顶点的正交多 边形最小看守数g 上( n ) ：k t jl n 4 j 对于联合看守的正交艺术画廊看守问题，m i c h a e l 和p i n c i u 在文献 1 4 中给 出了如下结论： 引理2 5 ( 联合看守的正交艺术画廊定理) 对任意甩26 的偶数，则具有疗 个顶点的正交简单多边形最小联合看守数跚( 刀) 茭b l n a j 第2 章预备知识 由于g g ( 3 ) = g g ( 4 ) = 2 ，并且g g 上( 4 ) = 2 ，也就是说对于取值小的数n ，不能应用 于引理2 5 引理2 6 【1 5 】如果q 是一个具有刀个顶点的四角剖分图( 咒6 ) ，那么 绍( 哪引 设g g 上( 只，k ) 是正交简单多边形的最少看守者数，并且每一个看守者至少看到 k 个其他的看守者 g g z ( n ，k ) = m a x g g 上( 只，后) i ：只是具有，1 个顶点的正交简单多边形) 可以得到以下结论： 咖2 1 5 】x c k 和蹦，g g a ( 咄m 忖l - 孚j 引理2 8 【2 4 ，2 5 】对带内壁的简单多边形看守集需要最少的看守数目为 m i n l ( 2 n - 3 ) 3 j ，l ( 2 m + n ) 3 j ，l ( 2 n + m ) 4 j ) 引理2 9 【2 6 1 对带内壁的正交简单多边形中的看守集需要最少的看守数目为 m i n l ( 以+ 2 m ) 4 j ，l o + s l 以2 j + m - 2 ) s j ) 第3 章艺术画廊看守者的顶点4 染色 3 13 染色 3 1 1 覆盖与三角剖分 通过对画廊的概念作形式化处理后，对于多边形内部的任何一点，只要连接 于它与某台监视器之间的开线段完全落在多边形的内部，它就能被这台监视器监 视到 为了覆盖一个简单多边形，需要多少台监视器呢? 显然，这要取决于具体的 多边形，多边形越是复杂，需要的监视器就越多因此，将根据多边形的顶点数目 n ，来限定所需监视器的数量然而，即使是顶点数目相等的两个多边形，其中的 一个，也可能比另一个更容易覆盖为了保险起见，所考虑的将是最坏的情况，也 就是说，将要给出的只是一个上限，该上限适用于由以个顶点组成的所有简单多边 形( 如果能够为特定的某个多边形找到其所需监视器的最小数目，而不是一个笼 统的最坏上限，那自然是再好不过的了，但不幸的是，“计算出特定多边形所需 监视器的最小数目”这一问题，是n p 难的) 设只为一个包含r 个顶点的简单多边形在确定为覆盖所需监视器的最小 数目时，由于的形状可能极为复杂，所以似乎无从下手于是首先将只分解为很 多块，每一块都很容易覆盖，具体而言，这里的“块 就是三角形为了完成这种 分解，需要添加一些对角线( d i a g o n a l ) ，将某些顶点对连接起来，所谓的对角线， 是一条开的线段，它连接于只的某两个顶点之间，而且完全落在的内部通过极 大的一组互不相交的对角线，可以将一个多边形分解为多个三角形，称之为该多 边形的一个三角剖分( t r i a n g u l a t i o n ) ，见图3 2 ( b ) ( 由于这一互不相交的对角线集 合必须满足最大化的条件，故可以保证任何三角形各边的内部，都不包含多边形 的任何顶点如果多边形中存在三个共线的顶点，就可能会出现这种情况) 通常， 一个简单多边形的三角剖分不是惟一的例如图3 2 ( a ) 所示的这个多边形，就有多 种不同的三角剖分方案( 图3 2 ( b ) 、( c ) ) 给定只的一个三角剖分7 ：l ，只要在( 由 此确定的) 每个三角形中放置一台监视器，就可以实现对整个多边形的覆盖然而， 艺术画廊4 _ 染色及联合看守问题研究 是否每个简单多边形总存在一个三角剖分呢? 如果存在，其中三角形的数目又是 多少呢? 引理2 2 回答了这些问题 ( a )( b )( c ) 图3 2 一个简单多边形及其可能的三角剖分 f i g 3 2as i m p l ep o l y g o na n di t sp o s s i b l et r i a n g u l a t i o n 3 1 2 三角剖分与二叉树对偶 在图论中与数据结构理论中，都有树的概念树的结构特点是由惟一起始点 “根( r o o t ) 开始的“结点 集合一个结点可以看作“双亲，它指向0 个、1 个或更多的称为“孩子 的结点没有孩子的结点称为“叶子 结点 二叉树作为一种特点的树，具有如下特点：每个结点有o 个、1 个或2 个孩子， 左边的结点称作“左孩子”，右边的结点称为“右孩子 多边形三角剖分可能存在很多结果，并且多边形完全可以按照二叉树的思想 进行三角剖分，即多边形可按二叉树结构进行分解，生成一个二叉树结构的三角 网同样也就说明了二叉树与三角剖分是对偶图 引理3 1 【2 刀具有n + 2 个顶点的简单多边形三角剖分与具有拧个结点的二叉树 对偶 对给定的简单多边形三角剖分，可以找到它的对偶图即具有一个结点的二叉 树三角剖分中每一个三角形与二叉树中的一个结点相对应亦即由简单多边形 三角剖分可以生成一棵二叉树首先，任选简单多边形三角剖分邻两结点及另一结 第3 章艺术画廊看守者的顶点禾染色 点建立的正确三角形为树根结点由于根三角形两顶点相邻，显而易见，根三角形 将原多边形分解为1 个或2 个子多边形三角剖分，并位于该三角形一侧或两侧然 后生成根三角形的左、右孩子三角形然后，以孩子三角形为双亲结点，向下递归 生成孩子三角形如当前三角形无孩子，即为叶子结点，则递归返回双亲结点如 双亲结点是上一级结点的左孩子时，则向下递归生成其右孩子子树，否则，向上 返回( 如图3 3 ) 根据引理3 1 ，对于一个给定的简单多边形三角剖分，可惟一得 到一棵二叉树与之对应 图3 3 简单多边形三角剖分与二叉树 f i g 3 3s i m p l ep o l y g o n st r i a n g u l a t i o na n db i n a r y t r e e 同样对于简单多边形的四角剖分来说，四角剖分q 是一个平面图，并且有偶 数个顶点如果把四角剖分中的一个小四边形看作一个点，两个相邻的四边形之 间有一条边，那么可以得出四角剖分q 的对偶图也是一棵树这棵树与二叉树的区 别在于，它有三个叉，每一个结点可向下分为左孩子，中孩子与右孩子也就是说 对于简单多边形的四角剖分，也可惟一得到一棵树与之对应 3 1 33 染色理论 由引理2 2 可以得出推论：包含万个顶点的任一简单多边形，都可以用 一2 台 监视器来覆盖然而，为每个三角形配备一台监视器，不免显得浪费比如，只要 将一台监视器安装在任何一条对角线上，就可以覆盖住与该对角线关联的两个三 艺术画廊4 染色及联合看守问题研究 角形上也就是说，如果精心挑选出若干条对角线，然后在那些位置安装监视器， 就可能将需监视器的总数减少到大约n 2 而似乎更好的策略是，将监视器安装在 ( 简单多边形) 顶点上毕竟，一个顶点可能同时与更多的三角相关联，于是，只 需要一台监视器就可以将与之相关联的所有三角形都覆盖住这样，就导出了下面 的方法 令乃为c 的一个三角剖分选出只的部分顶点组成一个子集，使瓦中的每个 三角形，都有至少一个顶点来自该子集；然后，在挑选出的每个顶点处，分别放 置一台监视器为了找出这样的一个子集，可以使用白、灰、黑三种颜色，给的 所有顶点染色( 如图3 4 所示) 所要求的染色方案必须满足：由任何边或者对角 线连接的两个顶点，所染的颜色不能相同，称之为“对经过三角剖分后的多边形 的3 染色( 3 c o l o r i n g ) 三角剖分后的多边形经过如此染色，其中每个三角形 都有且仅有一个白色、灰色、黑色的顶点因此，只在同色( 比如灰色) 的各顶点 处分别放置一台监视器，就必然可以覆盖整个多边形进一步地，若选用点数最少 的那一类同色顶点，并为它们配备监视器，则只需不超过ln 3i 台监视器，即可覆 盖住 图3 4 根据三角剖分对顶点进行3 一染色 f i g 3 43 - c o l o r i n g 嘶t l it r i a n g u l a t i o n 第3 章艺术画廊看守者的顶点4 - 染色 然而，3 染色方案是否总是存在昵? 答案是肯定的下面分析三角剖分正与其 对偶图二叉树的关系，记乙的对偶图二叉树为g ( 瓦) 对应于瓦中的每个三角形， g ( 疋) 都有一个顶点将对应于顶点，的三角形记作攻1 ，) 若“v ) 与攻“) 共用一条对 角线，则在v 和u 之间就设置一条弧这样，g ( z ) 中的各条弧就分别对应于中 的各条对角线任何一条对角线都会将e 一分为二，故移去g ( ) 的任意一条弧， g ( 瓦) 都会分裂成两个各自连通的部分因此，g ( ) 必然是一棵树当然，如果允 许多边形内含有空洞，这个结论就不一定成立，这样，只要对该图进行一次( 比 如，深度优先) 遍历，就可以得到一种3 染色的方案，接下来介绍一下具体做法， 在深度优先遍历的过程中，始终都要保证这样一点：已经访问过的三角形的所有 顶点，都已被染上了白色、灰色或黑色；而且，任何一对( 通过对角线或边) 相 互连接的顶点，颜色不能相同由此可以保证在访问完所有的三角形后，将得到一 个3 染色的方案，深度优先遍历可以从g ( ) 的任一顶点开始；第一个被访问的三 角形，其三个顶点将分别被染上白色、灰色或黑色( 不考虑次序) 现在，假设从 i 的一个顶点材到达另一个顶点谚既然如此，玎“) 与文力之间肯定存在一条公共的 对角线由于“v ) 的三个顶点都已经被染上了互异的颜色，所以“1 ，) 的三个顶点中 只有一个顶点需要染色而且，只有一种颜色可供这个顶点使用具体地说，也就 是“) 与“功之间的公共对角线没有使用的那种颜色因为g ( ) 是一棵树，所以在 此时，与1 ，相邻( 除“之外) 的其他顶点都还没有访问到，故而的确可以将剩下 的这种颜色赋给这个顶点( 如图3 5 ) 艺术画廊禾染色及联合看守问题研究 图3 53 染色方案必然存在 f i g 3 53 - c o l o r i n gm e t h o de x i s t 总之，对于经过三角剖分的任意简单多边形，都能够对其顶点实施3 染色于 是，只需要in 3i 台监视器，就可以覆盖住任何一个( 包含刀个顶点的) 简单多边 形不过，相应放置的监视器数目还可以更少毕竟，放置在顶点处的一台监视器， 其能够覆盖的范围，可能不止是与之相关联的那些三角形，然而不幸的是，对任 何厅3 ，都存在一个包含以个顶点的简单多边形，它的确需要ln 3i 台监视器这 样的一个例子就是所谓的“梳状多边形 ( c o m b - s h a p e dp o l y g o n ) 如图3 6 所示， 它有一条长长的水平基边，以及in 31 个分别由两条边形成的“梳齿 任何两个 相邻的梳齿之间，由一条水平边相连，只要适当地安排各顶点的位置，就总能保 证单台监视器无论放置在多边形内的什么位置，都不可能同时看到两个梳齿因 此，不能指望依靠某种策略，每次都找到少于in 3i 台监视器换言之，就最坏情 况而言，上述3 染色的方法已经是最优的了 第3 章艺术画廊看守者的顶点禾染色 n 3 个梳齿 图3 6 梳状力边形需要【- 胛3 j 台监视器 f i g 3 6c o m b - s h a p e dp o l y g o nw i t hv s i d e sn e e dl n 3 g u a r d s 由艺术画廊定理，现在可以得出，in 3l 台监视器总是够用的还要以利用有 效的算法，以计算出各台监视器的具体位置为此，可以利用a v i s 和t o u s s a i n 的 o ( n l o g n ) 时间内对简单多边形进行三角剖分的不同算法，以实现对任何简单多边 形的三角剖分；同时，通过上述算法，还可以导出一个合理的数据结构( 如，双 向链接边表) ，来表示三角剖分后的结果这样，在遍历时只需要常数时间，就可 以从一个三角形转到它的一个邻居一旦已经得到了这种形式的结构表示，就可以 在线性时间内，按照上述方法，深度优先遍历对偶图，完成3 染色，按照颜色将 所有顶点分成三类，取出数量最少的一类顶点，并在这类顶点处放置监视器，确 定总数不超过in 3i 台监视器的位置 3 24 染色方法 由三角剖分、3 一染色的方法及相关的染色规则，可以得出上述3 一染色的方法 在最坏的情况下是最优的但是3 一染色方法在有些时候并不是最优的，例如对一 个凸多边形而言，只需要一个看守就可以覆盖整个凸多边形，如果应用3 一染色方 法，可能得到的也是最坏的结果in 3i a g g a r w a l 5 1 以及l e e 和l i n t l 刀证明了“求任一简单多边形所需看守的最少数目 这一算法问题是n p 难的但可以通过其它的方法来确定放置监视器的位置使 艺术画廊4 _ 染色及联合看守问题研究 得其在绝大多数的情况下放置的监视器数目小于ln 31 下面利用三角剖分技术 对简单多边形进行三角剖分，然后分析由对角线分割的两个三角形之间的性质， 分析这两相邻三角形的邻接关系，给出下面两相邻三角形凸邻接与凹邻接的定义 定义3 1 在简单多边形的三角剖分中，如果两个三角形有一条公共边，那么 称这两个三角形是相邻接的如果两邻接的三角形构成的是凸四边形( 允许其中 一个角度为1 8 0 。) ，那么称这两个三角形是凸邻接，简记为彳；如果构成的是凹 四边形，那么称这两个三角形是凹邻接，简记为b ，如图3 7 ( a ) 凸邻接( b ) 凹邻接 图3 7 两个三角形的关系 f i g 3 7t w ot r i a n g l e sr e l a t i o n ( a ) p r o t r u d i n ga d j o i nc o ) c o n c a v ea d j o i n 由上述定义的两个相邻三角形凸邻接与凹邻接关系，定义4 一染色规则( 如图 3 8 所示) ： ( 1 ) 任意边或对角线连接的两个顶点所染颜色不能相同； ( 2 ) 如果两个相邻三角形是凸邻接，那么从一个三角形出发进行染色，首先 对这个三角形的三个顶点分别染三种不同的颜色，然后对其相邻的三角形中没有 对角线相邻的两个顶点中没有染色的点染第四种颜色； ( 3 ) 如果两个相邻三角形是凹邻接，那么从一个三角形出发进行染色，首先 对这