完全覆盖问题

《完全覆盖问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、区域覆盖问题摘要本论文主要是针对一个特定的矩形区域m*n(1000*1000)展开的，对该正方形区域进行分析，得知：要对矩形区域用圆进行覆盖即先需要对圆用多边形进行覆盖，由最小覆盖圆模型知，当且仅当用正多边形来限制圆的半径得到的圆可以使得覆盖整个图形时所用圆的个数最少。本文先证明问题一：一定半径（范围要求）的圆的内接正多边形可以完全覆盖该矩形区域，那么若干个该正多边形的外接圆能使得完全覆盖整个矩形区域所用圆的个数最少；再证明问题二:满足问题一限制条件的正多边形有正三角形正四边形正六边形。在适当的假设条件下，对假设的合理性进行说明和验证，得到了

2、题目所求的最优值。文中用到了几何知识、覆盖原理、微积分等一些数学知识探究了矩形覆盖的问题，通过计算机模拟分析了不同正多边形相交率变化趋势，最后运用matlab作出符合一般性的程序并得出相关图形。1.问题重述该题目讨论的是在一个特定的矩形区域（1000*1000）中,用半径为R的圆对其进行完全覆盖,要求相邻两个圆相交的公共面积不小于一个圆面积的K%,则应该如何覆盖可使得完全覆盖整个图形时所用圆的个数最少?则问题有如下几个方面:1.探究并证明正多边形的外接圆比不规则的多边形的外接圆的覆盖率要大；2.在满足条件的正多边形的外接圆的个数最少；3.假设

3、m=n=1000,r=100,则当k=5和k=18时，满足正多边的形状？124.由第3问的特殊情形探究一般情况并得到一般结论。2.模型的假设与符号约定2.1模型假设：1.区域中所有用于覆盖的圆是半径相等的圆。2.在区域中所有的地形是相对平整的，不考虑地形的影响。3.在覆盖过程中不考虑圆周长，半径及圆心的宽度。2.2符号约定：符号符号说明正多边形的内角度数x正多边形的边数y覆盖一个圆周所需的正多边形的个数正多边形的边所对的圆心角3问题的分析3.1圆的排列方式区域覆盖是指对一个指定区域，用一系列称为一跳覆盖区的小区域(圆)将其有重叠地完全覆盖。一

4、个有效的区域覆盖策略应能达到如下要求：(1)尽可能使全部一跳覆盖区半径之和为最小，即用最少的圆覆盖整个区域，这样才能节省节点资源。(2)各个节点覆盖范围的公共部分应满足一定的限制，以完成覆盖任务。上述区域划分问题是一个难题，在可以接受的多项式时间内得到最优解是不可能的，因为不可能穷举圆的任意形状的内接多边形来覆盖这个正方形区域，所以采用圆的内接正多边形覆盖方案，此即一个以正多边形为基本图形覆盖某一平面区域的问题。又有：定理1：若干半径为R的圆完全覆盖正方形区域的充分条件是这些圆的内接正多边形完全覆盖了正方形区域。证明：假设正n边形覆盖了正方形

5、区域中的，所有（i＝1，2，…，M），覆盖的区域包含了正方形区域B，即所有覆盖的区域包含了正方形区域B。因为对于由形成的外接圆，必包含区域，所以，所有（i＝1，2，…，M）覆盖的区域必包含了正方形区域B。定理2:两圆相交面积不小于两个圆中较大的圆面积的k％时，当两圆半径相等时，公共面积占两个圆总面积的百分比最小。12证明：如图两圆，半径因为，所以.又因为，所以.（当且仅当即时取等）。考虑在一个无限大的平面内采用两种半径，的圆相交完全覆盖平面。定义圆的有效利用率:则（当且仅当即时取等）。推论：两圆相交，满足相交面积不小于一个整圆面积的k％的条件

6、下，当两圆半径相等时，圆有效利用率最高。由定理2及推论得知，应选取半径相同的圆。3.2平面拼装的若干定义和定理：定义1如果一组图形拼铺后完全覆盖平面，并且这组图形没有重叠，则这组图形称为平面的拼装。定义2如果在平面的拼装中，只有一种基本元素图形，则称为平面的单元拼装；如果在单元拼装中基本元素图形为正多边形，则称为单元正规拼装；如果在单元拼装中基本元素图形为三角形，则称为单元三角拼装。定理3拼装中，其基本元素图形能且只能是正三角形、正方形和正六边形。现在我们来证明定理312证明：设在单元正规拼装中,其基本元素图形为正边形,正边形的每个内角值为,

7、显然，我们设（），则（1）解不定方程(1)可得:。即:在单元正规拼装中,其基本元素图形只可能是正三角形、正四边形、正六边形，因此，要使单元正规拼接的均匀覆盖效率最大，则应选择正三角形、正方形或正六边形拼接正方形区域。定理4在两等半径的圆相交的时候，若两交点夹的劣弧所对的圆心角固定，则相交面积与整个圆面积的比值与圆半径R无关，为常数。证明：如图1，两圆的圆心分别为，，半径均为R，两交点为A，B。相交面积为令①由①知，k值与圆的半径R无关，定理1得证。将中的化为数量12所以随着增大，k的值是单调增加的并且增长速度满足正弦形式。两半径相等圆相交，以

8、公共面积中心为坐标原点，圆心距。则两圆方程分别为:公共面积:令针对问题中的相交面积5％，18％两种情况，由上面公式计算出时，时，所以对于正六边形的外接圆而言，，此时