区域覆盖问题.docx

《区域覆盖问题.docx》由会员分享，可在线阅读，更多相关《区域覆盖问题.docx（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、圆掩盖矩形区域问题给定一个MxN的矩形区域，现用半径为的圆对其 进行完全掩盖，要求相邻两个圆相交的公共面积不小 于一个圆面积的z%,那么应如何掩盖可使得完全掩盖 整个图形时所用圆的个数最少（注：假如一个圆只有局部在图形中，也按一个计算）？例如，设 M = N = 1000、= 100,贝5j当攵=5和左=18时,结果如何？是否有一般性结论?摘要： 本文采用了分类争论思想方法，对如何合理地用圆对 矩形区域进行掩盖的问题进行了有效的分类争论，使 得对矩形区域进行完全掩盖所用圆的个数最少。其 次，采用了由一般及特别的方法，先得出一般结果， 从而归纳分类总结出一般规律，进而得出结论。再次, 对于这一问

2、题，采纳了先铺圆再放矩形的方式。最 终，将矩形进行了一系列平移，觉察当矩形的一些边 与圆与圆的相交弦重合时最优；而对于圆的放置，首 先选择了放置相交面积相等的圆，从而又觉察，对于 中间每个圆的全部弦形成的多边形恰为正多边形。最 终，由相交圆的面积满意不小于k%可以找到相应的多边形对应的边数。 关键词：矩形区域掩盖(i = 1,2,p;j = 1,2,q)当npj为偶数时有： 对于每列个数mPj：i=r + r+r + 2r+r + 2r-F r + 2r+ r N V2 k Jmpj1 1+ r + r + 2r + rdn2r+ r+ 厂 +(=厂且 hi 力为偶数kJV(怯1%解出:2r

3、+ 2N-42r4-V2 2r + 2N-42r m. k0/o7rr22 n2BP：27Sink%-7in n而对于一个相当大的矩形区域我们对其划分,将其划分为许多个正 多边形。那么这些正多边形应当具有刚好不重合地掩盖完整个矩形区域 （对于边界上的正多边形我们可不做要求刚好掩盖）。而对于正多边形的边数我们觉察：引理1在将矩形划分成正多边形中，正多边形能且只能是正三角 形、正四边形和正六边形。现在我们来证明引理1:证明：设在划分矩形为正n边形且n 3,正边形的每个内角值180。(-2)360a 二 x =为a,明显，我们设 a (x3,xe ),贝!)2n2x 个 4x =n = 2-1n 2

4、x 2x 2解方程得：x = 3, = 6;x = 4, = 4;x = 6, = 3o即：在将矩形划分成正三角形中只可能是正三角形、正四边形、正六边形，因此，应选择正三角形、正四边形或正六边形拼接矩形区域。现在我们对n取不同值时，争论k的临界值：方案一：当用正三角形划分矩形，即n=3时22TSink%-7r33解出临界点：ki=39.1002方案二：当用正四边形划分矩形，即n=4时22TSink%-7T44解出临界点：k2=18.1690方案三：当用正六边形划分矩形，即n=6时221- -Sink%-7T66解出临界点：k3=5.7669故而：、当 k2 al时，我们选择用正三角形来划分矩形

5、，所用正三角形的个数即为掩盖矩形所用最少圆 的个数。2 .当34人V自时,我们选择用正四边形来划分矩形，所用正四边形的个数即为掩盖矩形所用最少的个数。3.当0 4左时,我们选择用正六边形来划分矩形，所用正六边形的个数即为掩盖矩形所用最少圆 的个数。而对于给定圆与圆的相交面积为ko时，我们也可以 用以下不等式算出n的值27r27r27r-Sink%-7vSin（小、nn + 1n + 1 （）对于完全掩盖xN矩形圆个数的计算对于方案一，对于n=3时，即当k24 k 4k、时, 此时经过一系列验证，图形是不存在的。对于方案二，对于n=4,即当左3 V % V左2时，所用 个数：对于每列个数mpj：

6、mpj x42r N (m-l)pj x(mpj gN, j = ,23,.q)叵N ,1 6 N 口， 卡、解出m . M (m-1) x (miq e N*, i = 1,2,3,.)解出三；“外1+丁7且（外N）V2 M故而外=TVm m . x m.pq pj 峋_ 41 N 故而加网=TV_ 41 N 故而加网=TV41 M2 r对于方案三，对于n=6,即当。“左时，所 用圆个数为当npj为奇数时有： 对于每列个数mPj：11r + r + r + 2r + r + 2rd-2r + r+r + r N 414impj1 、 一-j=r+r + r + 2r + r + 2r-n2r+ 厂且勿:切为奇数解出:v3r + 2N-2y2r mni Mx出厂其中（多为奇数，=1,2,3,V2 MV2 A/ / 、/ * 一、解出 且（叫q为奇数） /irrui_i 2rl2 r-V2 M故而强尸TV当机均为偶数时，miq = miq_x +1所以用奇数行可以掩盖时，即p为奇数时F = mPj x 小+ x rn2iq