论文部分内容阅读
艺术画廊问题来源于实际生活,与简单多边形三角剖分是密不可分的,多年来,已经引起越来越多的研究者的关注.现如今,它在现实生活许多领域中都有着重要的应用.因为艺术画廊4-染色方法可以减少大部分简单多边形需要的看守数目,因此,无论在理论上还是在实际应用中,对其研究都具有重要的意义.
本文主要在3-染色的基础上研究艺术画廊4-染色问题,以及联合看守问题中一类特殊简单多边形的联合看守上限问题.
首先,在艺术画廊看守问题中,因为对绝大多数的简单多边形来说,由3-染色方法得到的结果并不是最优的.所以,本文根据三角剖分与二叉树的对应关系,通过分析三角剖分中两相邻三角形的邻接关系,利用染色的方法,提出4-染色方法以及4-染色规则,并对4-染色后的情况进行了分析与说明.得出任一类颜色的点覆盖整个简单多边形的条件、至少一类颜色的点覆盖整个简单多边形的条件,以及对不能覆盖产生的原因进行分析.
其次,在联合看守问题中,Michael得出了联合看守集合的上限应为[3n-l/7 ].本文通过对Michael证明过程以及相关结论的分析,首先将一个三角剖分Tn划分为两个三角剖分然后对三角剖分Tm进行分析,最后利用归纳法,对一类特殊的简单多边形,即简单多边形三角剖分的对偶图为链状的情况,证明了联合看守集合至少需要[2n/5]个联合看守.