区域覆盖问题.doc

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

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date区域覆盖问题模型假设：圆覆盖矩形区域问题给定一个的矩形区域，现用半径为的圆对其进行完全覆盖，要求相邻两个圆相交的公共面积不小于一个圆面积的，则应如何覆盖可使得完全覆盖整个图形时所用圆的个数最少（注：如果一个圆只有部分在图形中，也按一个计算）？ 例如，设、，则当和时，结果如何？是否有一般性结论？摘要：本文利用了分类讨论思想方法，对如何合理地用圆对矩形区域进行覆盖的问题进

2、行了有效的分类讨论, 使得对矩形区域进行完全覆盖所用圆的个数最少。其次，利用了由一般及特殊的方法，先得出一般结果，从而归纳分类总结出一般规律，进而得出结论。再次，对于这一问题， 采用了先铺圆再放矩形的方式。最后，将矩形进行了一系列平移，发现当矩形的一些边与圆与圆的相交弦重合时最优；而对于圆的放置，首先选择了放置相交面积相等的圆，从而又发现，对于中间每个圆的所有弦形成的多边形恰为正多边形。最后，由相交圆的面积满足不小于k%可以找到相应的多边形对应的边数。关键词：矩形区域 圆 覆盖1、问题重述:给定一个MxN的矩形区域，现用半径为r的圆对其进行完全覆盖，要求相邻两个圆相交的公共面积不小于一个圆面积

3、的k%。1、怎应如何覆盖可使得完全覆盖整个图形时所用圆的个数最少（注：如果一个圆只有部分在图形中，也按一个计算）？2、设M=N=1000，r=1 00，则当k=5和k=18时，结果如何？3、是否有一般性结论？2，模型的假设与符号说明:1.模型假设：1.圆与圆的相交面积相同（即相交弦长相等）2.当圆部分在矩形区域中时，仍算一个圆3.圆环系中的弦与矩形的某些边时重合的，若不重合我们也可以经过简单的平移，使得矩形的某些边与弦线重合2.符号：每个圆的半径 r最小相交圆面积占整个相交圆面积的百分比 k矩形的长 M 矩形的宽 N正多边形的边数 n每条弦所对应的圆心角每条弦的弦长 x弦到圆心的距离 d覆盖矩

4、形所需圆的个数 Mpq，p为列个数，q为行个数弦所对应的弧长 l扇形面积 S扇三角形面积 S三角相交圆面积 S相交3.模型的建立与求解1，圆的弦所对应的圆心角2，弦与圆心角关系3，扇形面积S扇4，三角形面积S三角5，相交面积S相交6，对于相交面积的关系 S扇S三角=S相交将以上式子整理即可得到：即： 而对于一个相当大的矩形区域我们对其划分，将其划分为很多个正多边形。则这些正多边形应该具有刚好不重合地覆盖完整个矩形区域（对于边界上的正多边形我们可不做要求刚好覆盖）。而对于正多边形的边数我们发现：引理1 在将矩形划分成正多边形中，正多边形能且只能是正三角形、正四边形和正六边形。现在我们来证明引理1

5、：证明：设在划分矩形为正n边形且 n 3, 正边形的每个内角值为, 显然，我们设（），则解方程得: 。即: 在将矩形划分成正三角形中只可能是正三角形、正四边形、正六边形，因此，应选择正三角形、正四边形或正六边形拼接矩形区域。现在我们对n取不同值时，讨论k的临界值：方案一：当用正三角形划分矩形，即n=3时解出临界点: k1=39.1002方案二：当用正四边形划分矩形，即n=4时解出临界点: k2=18.1690方案三：当用正六边形划分矩形，即n=6时解出临界点： k3=5.7669故而：1.当时，我们选择用正三角形来划分矩形，所用正三角形的个数即为覆盖矩形所用最少圆的个数。2.当时，我们选择用正

6、四边形来划分矩形，所用正四边形的个数即为覆盖矩形所用最少圆的个数。3.当时，我们选择用正六边形来划分矩形，所用正六边形的个数即为覆盖矩形所用最少圆的个数。而对于给定圆与圆的相交面积为k0时，我们也可以用以下不等式算出 n 的值 （）对于完全覆盖矩形圆个数的计算对于方案一，对于n=3时，即当时，此时经过一系列验证，图形是不存在的。对于方案二，对于n=4，即当时，所用圆个数：对于每列个数mpj：解出故而同理对于每行个数miq：解出故而故而对于方案三，对于n=6，即当时，所用圆个数为当为奇数时有：对于每列个数mpj： 解出： 故， 对于每行个数miq解出 故而 当 所以用奇数行可以覆盖时，即p为奇数

7、时 当为偶数时有：对于每列个数mpj：解出：故，所以用偶数行可以覆盖时，即p为偶数，此时总的个数为: 4对于当M=N=1000，r=1 00，则当k=5时，我们选择方案三计算，可得出所用总圆个数最少经验证p为奇数，故有 = =7而经简单计算得，偶数行的列数为8，而奇数行的列数为7所以：总的个数为: =如图：k=18时，我们选择方案二计算，可得出所用总圆个数最少故而而所以：如图：5，模型的推广此模型针对不同的 k值做出了不同的讨论，最后得出一般结论：当，用正六边形来划分矩形区域，当时，用正四边形来划分矩形区域，当时，是不存在这样的划分，即不存在这样的覆盖。而对于不等分隔圆时，我们可以由MxN来确定后进行每个相邻圆间相交面积相应的增调整，得出一般性规律。6，模型评价在求解区域覆盖时，对正三角性，正方行，正六边形的区域覆盖问题进行了讨论。在解决多边行等边界复杂图形时问题，遇到了一定的困难。在讨论时，运用编程作图相对比较麻烦。用几何画板作出了图形。7，模型的运用矩形作为数学覆盖问题 ,现已从另一角度提出了一种不同于有限元法的数值分析方法。该方法结构简单 ,不需要准备单元和结点数据 ,数据输入量少 ,能够很方便地实现与CAD技术的一体化。有限元法的通用性、有效性使得人们可以借助它来分析各种复杂的工程物理问题。-