完全覆盖问题

1区域覆盖问题摘要本论文主要是针对一个特定的矩形区域m*n(1000*1000)展开的，对该正方形区域进行分析，得知：要对矩形区域用圆进行覆盖即先需要对圆用多边形进行覆盖，由最小覆盖圆模型知，当且仅当用正多边形来限制圆的半径得到的圆可以使得覆盖整个图形时所用圆的个数最少。本文先证明问题一：一定半径（范围要求）的圆的内接正多边形可以完全覆盖该矩形区域，那么若干个该正多边形的外接圆能使得完全覆盖整个矩形区域所用圆的个数最少；再证明问题二:满足问题一限制条件的正多边形有正三角形正四边形正六边形。在适当的假设条件下，对假设的合理性进行说明和验证，得到了题目所求的最优值。文中用到了几何知识、覆盖原理、微积分等一些数学知识探究了矩形覆盖的问题，通过计算机模拟分析了不同正多边形相交率变化趋势，最后运用matlab作出符合一般性的程序并得出相关图形。1.问题重述该题目讨论的是在一个特定的矩形区域（1000*1000）中,用半径为R的圆对其进行完全覆盖,要求相邻两个圆相交的公共面积不小于一个圆面积的K%,则应该如何覆盖可使得完全覆盖整个图形时所用圆的个数最少?则问题有如下几个方面:1.探究并证明正多边形的外接圆比不规则的多边形的外接圆的覆盖率要大；2.在满足条件的正多边形的外接圆的个数最少；3.假设m=n=1000,r=100,则当k=5和k=18时，满足正多边的形状？24.由第3问的特殊情形探究一般情况并得到一般结论。2.模型的假设与符号约定2.1模型假设：1.区域中所有用于覆盖的圆是半径相等的圆。2.在区域中所有的地形是相对平整的，不考虑地形的影响。3.在覆盖过程中不考虑圆周长，半径及圆心的宽度。2.2符号约定：符号符号说明正多边形的内角度数x正多边形的边数y覆盖一个圆周所需的正多边形的个数正多边形的边所对的圆心角3问题的分析3.1圆的排列方式区域覆盖2是指对一个指定区域，用一系列称为一跳覆盖区的小区域(圆)将其有重叠地完全覆盖。一个有效的区域覆盖策略应能达到如下要求：(1)尽可能使全部一跳覆盖区半径之和为最小，即用最少的圆覆盖整个区域，这样才能节省节点资源。(2)各个节点覆盖范围的公共部分应满足一定的限制，以完成覆盖任务。上述区域划分问题是一个难题，在可以接受的多项式时间内得到最优解是不可能的，因为不可能穷举圆的任意形状的内接多边形来覆盖这个正方形区域，所以采用圆的内接正多边形覆盖方案，此即一个以正多边形为基本图形覆盖某一平面区域的问题。又有：定理1：若干半径为R的圆完全覆盖正方形区域的充分条件是这些圆的内接正多边形完全覆盖了正方形区域。证明：假设正n边形iA覆盖了正方形区域中的iB，所有iA（i＝1，2，…，M），覆盖的区域包含了正方形区域B，即所有iB覆盖的区域包含了正方形区域B。因为对于由iA形成的外接圆iO，必包含区域iB，所以，所有iO（i＝1，2，…，M）覆盖的区域必包含了正方形区域B。定理2:两圆相交面积不小于两个圆中较大的圆面积的k％时，当两圆半径相等时，公共面积占两个圆总面积的百分比最小。3证明：如图两圆，半径12RR³因为12RR³，所以12ooSS³.又因为11%oSkS=，所以12%oSkS³.2121%2%1ooooSkkSSSS=?++（当且仅当12ooSS=即12RR=时取等）。考虑在一个无限大的平面内采用两种半径1R，2R的圆相交完全覆盖平面。定义圆的有效利用率:h=实际两圆在平面内占的面积两圆总面积则12121021%%111%21ooooooSSkSkkSSSSh+-=-?++＝（当且仅当12ooSS=即12RR=时取等）。推论：两圆相交，满足相交面积不小于一个整圆面积的k％的条件下，当两圆半径相等时，圆有效利用率最高。由定理2及推论得知，应选取半径相同的圆。3.2平面拼装的若干定义和定理：定义1如果一组图形拼铺后完全覆盖平面，并且这组图形没有重叠，则这组图形称为平面的拼装。定义2如果在平面的拼装中，只有一种基本元素图形，则称为平面的单元拼装；如果在单元拼装中基本元素图形为正多边形，则称为单元正规拼装；如果在单元拼装中基本元素图形为三角形，则称为单元三角拼装。定理3拼装中，其基本元素图形能且只能是正三角形、正方形和正六边形。现在我们来证明定理34证明：设在单元正规拼装中,其基本元素图形为正(3)xx³边形,正x边形的每个内角值为,显然180(2)xxa?=，我们设360ya=（3,yyN澄），则2242222xyyxxyy=?=+---（1）解不定方程(1)可得:3,6;4,4;6,3yxyxyx======。即:在单元正规拼装中,其基本元素图形只可能是正三角形、正四边形、正六边形，因此，要使单元正规拼接的均匀覆盖效率最大，则应选择正三角形、正方形或正六边形拼接正方形区域。定理4在两等半径的圆相交的时候，若两交点夹的劣弧所对的圆心角固定，则相交面积1S与整个圆面积S的比值与圆半径R无关，为常数。证明：如图1，两圆的圆心分别为1o，2o，半径均为R，两交点为A，B。相交面积为22112sin3602SRRqpq轾=-犏犏臌令2212sinsin180180RRSkSRqpqqpp-===-①由①知，k值与圆的半径R无关，定理1得证。将sin中的化为数量sin1805sin1180()(1cos)0180180180dkdddqpqqpqqp=-=-所以随着增大，k的值是单调增加的并且增长速度满足正弦形式。两半径相等圆相交，以公共面积中心为坐标原点，圆心距2da=。则两圆方程分别为:222()xayR-+=222()xayR++=公共面积:02204*()aRSRxadx-=--ò令xat-=xta=+2204*aRSRtdt--=-òarcsin22024*cosaRSRdpqq--=ò22222002arcsin2aSRRaRakRRpp=---=针对问题中的相交面积5％，18％两种情况，由上面公式计算出15%SkS==时，57.1q=118%SkS==时，89.7q=所以对于正六边形的外接圆而言，6057.1q=，此时15.77%SkS==，所以，用正六边形的外接圆作为模型所需的圆建立的模型可以很好的解决公共面积不小于5％的要求。同理可知，对于正四边形的外接圆而言，9089.7q=，此时，118.17%SkS==所以，用正四边形的外接圆作为模型所需的圆建立的模型可以很好的解决公共面积不小于18％的要求。64.模型的建立与求解1用半径为r=100的圆如何完全覆盖整个矩形区域（10001000），使得相邻两圆相交的公共面积不小于一个圆面积的k％。因此，我们用正多边形来覆盖则需讨论用什么类型的正多边形和什么方式覆盖4.1正多边形的类型EquationSection(Next)由多边形的内角和公式可得正多边形的一个内角，即(2)180(3,)oxxxNxa-?=澄、360(3,)oyyyNa=澄，解得：22xyx=-所以：y643x346则满足完全覆盖条件的正多边形只有正三边形、正四边形、正六边形。4.2正多边形的覆盖方式由于相邻两圆相交的公共面积不小于一个圆面积的k％,现在设一个圆的内接正多边形的边所对的圆心角为，由面积之间的关系()则可得关于k的不等式：sin360(,3,4,6)okxxqqqpp-?=当3x=时120oq=，则k=39.09当4x=时90oq=，则k=18.15当6x=时60oq=，则k=5.77由题可得：当k=5时，三种正多边形都满足条件；当k=18时，只有正四边形和正六边形满足条件。而用正三角形的外接圆覆盖区域时，其相邻两圆相交的公共面积为一个圆面积的39.09％，故其相交的面积过大，则在同等矩形内所需的圆的个数更多不符合题中所要求的圆的个数最少的条件，所以，我们只需讨论正四边形和正六边形。经过重复实验过后，我们得出了两种正多边形的最优覆盖方式：①用正四边形覆盖覆盖整个矩形区域只需半径为100的圆64个，其覆盖的图形如图1所示。7-20002004006008001000120001002003004005006007008009001000正四边形完全覆盖图图1②用正六边形覆盖覆盖整个矩形区域只需半径为100的圆45个，其覆盖的图形如图2所示。8-20002004006008001000-200020040060080010001200正六边形完全覆盖图图25.模型的分析由第四节中的讨论我们可知：满足完全覆盖条件的正多边形只有正三角形、正四边形、正六边形；而我们只讨论k=5和k=8的情况，实际上k是一个的可控因素，根据不同情况来决定；因此我们探究一般性结论，由第四节可得：正多边形346K的取值39.09％18.15％5.77％则只需5.77k³，就可以根据实际情况找到一种完全覆盖一个给定的mn矩形的最优方式，其变化趋势如图3934567891000.050.10.150.20.250.30.350.4正多边形相交率K％的变化趋势图图36．模型的评价及改进6.1模型的评价⑴本模型运用了几何知识等数学方法。⑵模型讨论了一定条件下的完全覆盖问题可以为实际情况提供一些定量分析。⑶该模型虽具有一般性，但并不是所有情况都适用。6.2模型的改进我们先通过具体的实例来讨论区域覆盖问题，使得问题较为简单、直观，而实际情况还有诸多相关因素与要讨论的问题相互制约；在现在的经济社会中，应该加以考虑使用的圆的半径为多少时，能使覆盖矩形的圆的面积最少，而我们只讨论了k（相邻两圆相交的公共面积不小于一个圆面积的k％）的变动情况，还有待于改进讨论方向。参考文献[1]姜启源,谢金星,叶俊.数学模型（第三版），高等教育出版社。[2]杨中华.平面点列最小覆盖圆的计算方法，北京工业大学学报，2000,vol.26(2).10附录附录1、判断哪些正多边形能够完全覆盖的程序fori=3:1000;m(i)=i;n(i)=2*m(i)/(m(i)-2);ifmod(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;fori=0:r*sqrt(2):mforj=0:r*sqrt(2):nx=i+r*cos(th);y=j+r*sin(th);plot(x,y,'k')holdonaxisequalendendholdonfori=0:(m/(r*sqrt(2)))forj=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)])endendholdonrectangle('Position',[0,0,m,n],'EdgeColor','r')holdonrectangle('Position',[-r*sqrt(2)/2,-r*sqrt(2)/2,m,n],'EdgeColor','b')附录3、正六边形完全覆盖程序clear;clcr=input('请输入圆的半径r=');m=input('请输入宽m=');11n=input('请输入高n=');rc=r*sqrt(3)/2;dy=2*rc;dx=rc*sqrt(3);A=pi/3*[1:7];foryk=[0:dy:n,0:-dy:-n];yfun=inline(['sqrt(3)*x/3+',num2str(yk)]);forxk=[0:dx:m,0:-dx:-m];xp=xk;yp=yfun(xp);if-rxp&xpm&-ryp&ypn;plot([xp+i*yp]+rc*exp(i*A)*2/sqrt(3),'k','linewidth',2)holdon;plot(xp,