完全覆盖问题.doc

区域覆盖问题摘要 本论文主要是针对一个特定的矩形区域m*n(1000*1000)展开的，对该正方形区域进行分析，得知：要对矩形区域用圆进行覆盖即先需要对圆用多边形进行覆盖，由最小覆盖圆模型知，当且仅当用正多边形来限制圆的半径得到的圆可以使得覆盖整个图形时所用圆的个数最少。本文先证明问题一：一定半径（范围要求）的圆的内接正多边形可以完全覆盖该矩形区域，那么若干个该正多边形的外接圆能使得完全覆盖整个矩形区域所用圆的个数最少；再证明问题二:满足问题一限制条件的正多边形有正三角形正四边形正六边形。在适当的假设条件下，对假设的合理性进行说明和验证，得到了题目所求的最优值。 文中用到了几何知识、覆盖原理、微积分等一些数学知识探究了矩形覆盖的问题，通过计算机模拟分析了不同正多边形相交率变化趋势，最后运用matlab作出符合一般性的程序并得出相关图形。1.问题重述该题目讨论的是在一个特定的矩形区域（1000*1000）中,用半径为R的圆对其进行完全覆盖,要求相邻两个圆相交的公共面积不小于一个圆面积的K%,则应该如何覆盖可使得完全覆盖整个图形时所用圆的个数最少?则问题有如下几个方面:1.探究并证明正多边形的外接圆比不规则的多边形的外接圆的覆盖率要大；2.在满足条件的正多边形的外接圆的个数最少；3.假设m=n=1000,r=100,则当k=5和k=18时，满足正多边的形状？4.由第3问的特殊情形探究一般情况并得到一般结论。2.模型的假设与符号约定2.1模型假设：1.区域中所有用于覆盖的圆是半径相等的圆。2.在区域中所有的地形是相对平整的，不考虑地形的影响。3.在覆盖过程中不考虑圆周长，半径及圆心的宽度。2.2 符号约定：符号符号说明正多边形的内角度数x正多边形的边数y覆盖一个圆周所需的正多边形的个数正多边形的边所对的圆心角3 问题的分析3.1 圆的排列方式区域覆盖是指对一个指定区域，用一系列称为一跳覆盖区的小区域(圆)将其有重叠地完全覆盖。一个有效的区域覆盖策略应能达到如下要求：(1)尽可能使全部一跳覆盖区半径之和为最小，即用最少的圆覆盖整个区域，这样才能节省节点资源。(2)各个节点覆盖范围的公共部分应满足一定的限制，以完成覆盖任务。上述区域划分问题是一个难题，在可以接受的多项式时间内得到最优解是不可能的，因为不可能穷举圆的任意形状的内接多边形来覆盖这个正方形区域，所以采用圆的内接正多边形覆盖方案，此即一个以正多边形为基本图形覆盖某一平面区域的问题。又有：定理1：若干半径为R的圆完全覆盖正方形区域的充分条件是这些圆的内接正多边形完全覆盖了正方形区域。证明：假设正n边形覆盖了正方形区域中的，所有（i1，2，M），覆盖的区域包含了正方形区域B，即所有覆盖的区域包含了正方形区域B。因为对于由形成的外接圆，必包含区域，所以，所有（i1，2，M）覆盖的区域必包含了正方形区域B。定理2: 两圆相交面积不小于两个圆中较大的圆面积的k时，当两圆半径相等时，公共面积占两个圆总面积的百分比最小。证明：如图两圆，半径因为 ，所以 .又因为 ，所以 . （当且仅当即时取等）。考虑在一个无限大的平面内采用两种半径，的圆相交完全覆盖平面。定义圆的有效利用率: 则（当且仅当即时取等）。 推论：两圆相交，满足相交面积不小于一个整圆面积的k的条件下，当两圆半径相等时，圆有效利用率最高。由定理2及推论得知，应选取半径相同的圆。3.2 平面拼装的若干定义和定理： 定义1 如果一组图形拼铺后完全覆盖平面，并且这组图形没有重叠，则这组图形称为平面的拼装。 定义2 如果在平面的拼装中，只有一种基本元素图形，则称为平面的单元拼装；如果在单元拼装中基本元素图形为正多边形，则称为单元正规拼装；如果在单元拼装中基本元素图形为三角形，则称为单元三角拼装。 定理3 拼装中，其基本元素图形能且只能是正三角形、正方形和正六边形。现在我们来证明定理3 证明：设在单元正规拼装中, 其基本元素图形为正边形, 正边形的每个内角值为, 显然 ，我们设（），则 （1）解不定方程(1)可得: 。即: 在单元正规拼装中, 其基本元素图形只可能是正三角形、正四边形、正六边形，因此，要使单元正规拼接的均匀覆盖效率最大，则应选择正三角形、正方形或正六边形拼接正方形区域。 定理4 在两等半径的圆相交的时候，若两交点夹的劣弧所对的圆心角固定，则相交面积与整个圆面积的比值与圆半径R无关，为常数。证明：如图1，两圆的圆心分别为，半径均为R，两交点为A，B。相交面积为 令 由知，k值与圆的半径R无关，定理1得证。将中的化为数量 所以随着增大，k的值是单调增加的并且增长速度满足正弦形式。两半径相等圆相交，以公共面积中心为坐标原点，圆心距。则两圆方程分别为: 公共面积: 令 针对问题中的相交面积5，18两种情况，由上面公式计算出 时， 时，所以对于正六边形的外接圆而言，此时，所以，用正六边形的外接圆作为模型所需的圆建立的模型可以很好的解决公共面积不小于5的要求。同理可知，对于正四边形的外接圆而言， ，此时，所以，用正四边形的外接圆作为模型所需的圆建立的模型可以很好的解决公共面积不小于18的要求。4. 模型的建立与求解 用半径为r =100的圆如何完全覆盖整个矩形区域（10001000），使得相邻两圆相交的公共面积不小于一个圆面积的k。因此，我们用正多边形来覆盖则需讨论用什么类型的正多边形和什么方式覆盖4.1 正多边形的类型由多边形的内角和公式可得正多边形的一个内角 ，即 、，解得： 所以： y643x346则满足完全覆盖条件的正多边形只有正三边形、正四边形、正六边形。4.2 正多边形的覆盖方式 由于相邻两圆相交的公共面积不小于一个圆面积的k,现在设一个圆的内接正多边形的边所对的圆心角为，由面积之间的关系()则可得关于k的不等式： 当时 ，则k=39.09 当时 ，则k=18.15 当时 ，则k=5.77由题可得：当k=5时，三种正多边形都满足条件；当k=18时，只有正四边形和正六边形满足条件。 而用正三角形的外接圆覆盖区域时，其相邻两圆相交的公共面积为一个圆面积的39.09，故其相交的面积过大，则在同等矩形内所需的圆的个数更多不符合题中所要求的圆的个数最少的条件，所以，我们只需讨论正四边形和正六边形。 经过重复实验过后，我们得出了两种正多边形的最优覆盖方式： 用正四边形覆盖 覆盖整个矩形区域只需半径为100的圆64个，其覆盖的图形如图1所示。图1 用正六边形覆盖 覆盖整个矩形区域只需半径为100的圆45个，其覆盖的图形如图2所示。图25.模型的分析由第四节中的讨论我们可知：满足完全覆盖条件的正多边形只有正三角形、正四边形、正六边形；而我们只讨论k=5和k=8的情况，实际上k是一个的可控因素，根据不同情况来决定；因此我们探究一般性结论，由第四节可得：正多边形346K的取值39.0918.155.77则只需，就可以根据实际情况找到一种完全覆盖一个给定的矩形的最优方式，其变化趋势如图3 正多边形相交率K的变化趋势图图36模型的评价及改进6.1 模型的评价 本模型运用了几何知识等数学方法。 模型讨论了一定条件下的完全覆盖问题可以为实际情况提供一些定量分析。 该模型虽具有一般性，但并不是所有情况都适用。6.2 模型的改进 我们先通过具体的实例来讨论区域覆盖问题，使得问题较为简单、直观，而实际情况还有诸多相关因素与要讨论的问题相互制约；在现在的经济社会中，应该加以考虑使用的圆的半径为多少时，能使覆盖矩形的圆的面积最少，而我们只讨论了k（相邻两圆相交的公共面积不小于一个圆面积的k）的变动情况，还有待于改进讨论方向。参考文献1 姜启源,谢金星,叶俊. 数学模型（第三版），高等教育出版社。2 杨中华. 平面点列最小覆盖圆的计算方法，北京工业大学学报，2000,vol.26(2) .附录附录1、判断哪些正多边形能够完全覆盖的程序for i=3:1000; m(i)=i; n(i)=2*m(i)/(m(i)-2); if mod(n(i),1)=0; disp(m=,num2str(m(i), n=,num2str(n(i) endend附录2、正四边形完全覆盖程序r=input(请输入圆的半径r=);m=input(请输入宽m=);n=input(请输入高n=);th=0:0.1:2*pi;for i=0:r*sqrt(2):mfor j=0:r*sqrt(2):n x=i+r*cos(th); y=j+r*sin(th); plot(x,y,k) hold on axis equalendendhold onfor i=0:(m/(r*sqrt(2)for j=0:(n/(r*sqrt(2) x=-r*sqrt(2)/2+r*sqrt(2)*i; y=-r*sqrt(2)/2+r*sqrt(2)*j;rectangle(Position,x,y,r*sqrt(2),r*sqrt(2)endendhold onrectangle(Position,0,0,m,n,EdgeColor,r)hold onrectangle(Position,-r*sqrt(2)/2,-r*sqrt(2)/2,m,n,EdgeColor,b)附录3、正六边形完全覆盖程序clear;clcr=input(请输入圆的半径r=);m=input(请输入宽m=);n=input(请输入高n=);rc=r*sqrt(3)/2;dy=2*rc;dx=rc*sqrt(3);A=pi/3*1:7;for yk=0:dy:n,0:-dy:-n; yfun=inline(sqrt(3)*x/3+,num2str(yk