区域覆盖问题

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

1、区域覆盖问题王茜薛波王友春指导教师冯世强摘要本文针对区域覆盖问题，提出用半径相同的最少的圆完全覆盖整个矩形区域，题中明确要求相邻两个圆相交的公共面积不少于一个圆面积的k%。这样用最少的圆覆盖矩形区域，比起一般情况下的覆盖减少了圆的使用个数，在固定的区域内用最少的资源，节约资源。针对本问题的求解，我们主要运用数学中的大量几何知识加上代数运算来进行解答。首先，对于矩形区域覆盖问题，我们根据给出的实际数据采用特殊的求解方法，建立以正方形为基础，用正方形外接圆为单位对矩形区域进行覆盖的模型I,然后在对模型I改进的基础上，建立以正六边形为基础，用正六边形外接圆为单位对矩形区域进行覆盖的模型

2、II。结合本题中所给的一组数据对所给出的模型进行检验和分析，最后结合模型I、II.最后推广到以圆为单位对矩形区域进行覆盖，借助于图形的数学算法和MATLAB软件，得到最优求解模型。关键词：区域覆盖外接圆正六边行正方形MATLAB目录一、问题重述二、问题分析一、模型假设二、定义与符号说明三、模型的建立与求解模型I(正方形模型)模型II(正六边形模型)推广：以圆求解模型四、对模型的评价五、参考文献六、附录一﹑问题重述给定一个m*n的矩形区域，如果半径为r的圆对其进行完全覆盖，要求相邻两个圆相交的公共面积不小于一个圆面积的k%，使得完全覆盖整个图形时所用圆的个数最少，求解覆盖模型。二﹑

3、问题分析对于问题的分析，要求我们要完全相同的最少的圆完全覆盖矩形区域，这样减少圆的个数，让其求解该题的思路更加清晰。该问题属于数学中的几何问题，通常采用几何作图的方法再结合几何定理尝试解决该问题的模型，再通过具体数据对模型进行验证优化，筛选出最优模型。对于问题所要求的结果进行分析：题目要求使用尽可能少的完全相同的圆完全覆盖矩形区域，要使其完全覆盖则圆与圆之间必有重叠部分。基于上述要求，本题就从减少重叠部分着手。又因为此题给出了一组数据，利用数据可使得问题简化。从实际结合理论要求，我们采用预测、推理、证明的方法。首先，正方形是一个特殊的四边形，用圆进行覆盖，把两个特殊的图形联系起来

4、。很自然的想到利用正方形进行覆盖，而用正方形的外接圆再覆盖矩形区域。再从具体的数据入手计算，考虑完全覆盖的最优个数问题。那么其他的正多边形是否可以同样利用外接圆的思想对矩形区域进行完全覆盖计算？通过证明可以知道正三角形、正方形、正六边形可以满足要求（见附录1.2）。利用几何定理自然地可以推广到正六边形。这就是本文的基本思路。综合以上原因，首先，我们建立了一个以正方形为单位对矩形区域进行覆盖的模型I，然后，建立了一个以正六边形为单位的对矩形区域进行覆盖的模型II。先对两个模型进行预测，再利用所给的实际数据进行计算，对结果进行了分析。最后，得出较优模型。三、模型假设⑴．覆盖区域为一个

5、矩形;⑵．每一个圆都是半径相同的等圆；⑶．相邻两个圆相交的公共面积不小于一个圆面积的k%;⑷.如果一个圆只有部分在图形中，也按一个计算；⑸．用相同的正多边形完全覆盖矩形，相邻正多边形间无缝隙。四、定义与符号说明M矩形区域的长N矩形区域的宽r外接圆的半径K%相邻两个圆相交的公共面积所占一个圆面积的百分比A1矩形长所包含的正六边形的个数B1矩形宽所包含的正六边形的个数A2矩形长所包含的正方形的个数B2矩形宽所包含的正方形的个数c覆盖矩形所用的正多边形个数S1两个正多边形外接圆相交的重合面积S一个正多边形外接圆面积模型的建立与求解一以正方形为单位的对矩形区域进行覆盖的模型I在解决本问题

6、的过程中，我们需要考虑的问题主要有以下几点：一、怎样用圆覆盖矩形区域，且使得所用圆的个数最少？二、相邻两个圆重合面积的怎样计算？由于题中最后给出了一边长为1000的正方形，半径为100的圆去填充正方形，故我们可以通过该特殊例子的求解方案建立模型，从而推广到一般的矩形区域覆盖问题。针对m=n=1000.r=100,的覆盖问题的求解解题思路如下：建立以正方形为基础，通过以正方形外接圆为单位去覆盖例题中所给的正方形，然后根据例题作进一步的推广到矩形。如下图所示小正方形的对角线ab为200，则可以通过计算得到小正方形的边长为100（注1.4142）小正方形的外接圆半径r=100，用小正方

7、形外接圆去覆盖小正方形。当正方形边长为1000时，可以将此正方形分解为对角线长为200的若干小正方形，没有被分为小正方形部分为小矩形，然后用小正方形的外接圆去覆盖小正方形，剩余的小矩形补为对角线长为200的小正方形，然后用小正方形外接圆去覆盖小正方形。通过编程得到（附录3）如下图共要8*8=64个小方形此时相邻两正方形外接圆重合面积为S1如下图所示S1=()S=K%==18.15%以上是对边长为1000的正方形的计算，通过该计算思想可以推广到矩形区域覆盖问题上已知矩形的长为m，宽