最新2016区域覆盖问题设计报告

目录

一、 问题重述

二、 问题分析

三、 模型假设

四、 定义与符号说明

五、 模型的建立与求解

模型I(正方形模型)

模型II(正六边形模型)

推广 ：以圆求解模型

六、 对模型的评价

七、 参考文献

八、 附录

一﹑问题重述

给定一个m*n的矩形区域，如果半径为r 的圆对其进行完全覆盖，要求相邻两个圆相交的公共面积不小于一个圆面积的k%，使得完全覆盖整个图形时所用圆的个数最少，求解覆盖模型。

二﹑问题分析

对于问题的分析，要求我们要完全相同的最少的圆完全覆盖矩形区域，这样减少圆的个数，让其求解该题的思路更加清晰。该问题属于数学中的几何问题，通常采用几何作图的方法再结合几何定理尝试解决该问题的模型，再通过具体数据对模型进行验证优化，筛选出最 1

优模型。

对于问题所要求的结果进行分析：题目要求使用尽可能少的完全相同的圆完全覆盖矩形区域，要使其完全覆盖则圆与圆之间必有重叠部分。基于上述要求，本题就从减少重叠部分着手。又因为此题给出了一组数据，利用数据可使得问题简化。从实际结合理论要求，我们采用预测、推理、证明的方法。首先，正方形是一个特殊的四边形，用圆进行覆盖，把两个特殊的图形联系起来。很自然的想到利用正方形进行覆盖，而用正方形的外接圆再覆盖矩形区域。再从具体的数据入手计算，考虑完全覆盖的最优个数问题。那么其他的正多边形是否可以同样利用外接圆的思想对矩形区域进行完全覆盖计算？通过证明可以知道正三角形、正方形、正六边形可以满足要求（见附录1.2）。利用几何定理自然地可以推广到正六边形。这就是本文的基本思路。 综合以上原因，首先，我们建立了一个以正方形为单位对矩形区域进行覆盖的模型I ，然后，建立了一个以正六边形为单位的对矩形区域进行覆盖的模型II 。先对两个模型进行预测，再利用所给的实际数据进行计算，对结果进行了分析。最后，得出较优模型。

三、模型假设

⑴．覆盖区域为一个矩形;

⑵．每一个圆都是半径相同的等圆；

⑶．相邻两个圆相交的公共面积不小于一个圆面积的k%;

⑷. 如果一个圆只有部分在图形中，也按一个计算；

⑸．用相同的正多边形完全覆盖矩形，相邻正多边形间无缝隙。

四、定义与符号说明

2

模型的建立与求解

一 以正方形为单位的对矩形区域进行覆盖的模型I

在解决本问题的过程中，我们需要考虑的问题主要有以下几点：

一、怎样用圆覆盖矩形区域，且使得所用圆的个数最少？二、相邻两个圆重合面积的怎样计算？由于题中最后给出了一边长为1000的正方形，半径为100的圆去填充正方形，故我们可以通过该特殊例子的求解方案建立模型，从而推广到一般的矩形区域覆盖问题。 针对m=n=1000.r=100,的覆盖问题的求解

解题思路如下：

建立以正方形为基础，通过以正方形外接圆为单位去覆盖例题中所给的正方形，然后根据例题作进一步的推广到矩形。如下图所示

小正方形的对角线ab 为200，则可以通过计算得到小正方形的边长 3

为1002≈141. 42 （注2≈1.4142）小正方形的外接圆半径r=100，用小正方形外接圆去覆盖小正方形。当正方形边长为1000时，可以将此正方形分解为对角线长为200的若干小正方形，没有被分为小正方形部分为小矩形，然后用小正方形的外接圆去覆盖小正方形，剩余的小矩形补为对角线长为200的小正方形，然后用小正方形外接圆去覆盖小正方形。通过编程得到（附录3）如下图

共要8*8=64个小方形

此时相邻两正方形外接圆重合面积为S1 如下图所示

222S1=(πr ⨯-r ⨯) ⨯2 S=πr 1

412

4

K%=S 1

S =18.15%

以上是对边长为1000的正方形的计算，通过该计算思想可以推广到矩形区域覆盖问题上

已知矩形的长为m ，宽为 n ，用半径为 r的圆去覆盖矩形，可把矩形分成若干个对角线长为2r 的小正方形，没有被分为小正方形部分为小矩形，然后用小正方形的外接圆去覆盖小正方形，剩余剩余的小矩形补为对角线长为200的小正方形，然后用小正方形外接圆去覆盖小正方形。建立如下公式 ⎧m m ⎡m ⎤ -⎪⎢⎥=0r 2r 2⎣r 2⎦A2=⎪ ⎨⎪⎡m ⎤+1 m -⎡m ⎤>0⎥⎢⎥⎪⎢r 2⎣r 2⎦⎩⎣r 2⎦

⎧n n ⎡n ⎤ -⎪⎢⎥=0r 2r 2⎣r 2⎦B2=⎪ ⎨⎪⎡n ⎤n +1 n -⎡n ⎤>0⎥⎢⎥⎪⎢r 2⎣r 2⎦⎩⎣r 2⎦

⎧m ⎛m ⎛n n ⎡m ⎤⎫⎡n ⎤⎫⎪ ⨯ -=0且-=0⎪⎢⎥⎪⎢⎥⎪ ⎪⎝r 2⎣r 2⎦⎭⎝r 2⎣r 2⎦⎭⎪r 2r 2

⎪⎛m ⎛n ⎡n ⎤⎫⎡m ⎤⎫⎡n ⎤⎫⎪m ⨯⎛ ⎪ ⎪ ⎪+1 -=0且-⎢⎥⎢⎥⎢⎥ ⎪ ⎪ ⎪>0⎪r 2r 2r 2r 2r 2r 2⎦⎭⎣⎦⎭⎣⎦⎭ ⎪⎝⎣⎝⎝⎨⎛⎡m ⎤⎫⎛n ⎛m ⎡n ⎤⎫⎡m ⎤⎫⎪n ⎪ ⎪ ⨯+1 -=0且- r 2⎢r 2⎥⎪ r 2⎢r 2⎥⎪⎪>0⎪r 2 ⎢r 2⎥⎪⎦⎭⎣⎦⎭⎣⎦⎭⎝⎣⎝⎝⎪⎪⎛⎡n ⎤⎫⎛⎡m ⎤⎫⎛n ⎛m ⎡n ⎤⎫⎡m ⎤⎫ ⎪ ⎪ ⎪ +1⨯+1 ->0且->0⎪ ⎢⎥⎪ ⎢⎥⎪⎢⎥⎪⎢⎥⎪ ⎪⎪⎝r 2⎣r 2⎦⎭⎝r 2⎣r 2⎦⎭⎩⎝⎣r 2⎦⎭⎝⎣r 2⎦⎭S=A2*B2=

根据以上公式我们可以通过编程计算出要用多少个圆去覆盖矩形，该求解该模型的思路和求解上一特例的思路一样，即相邻两正方形外接圆重合面积与上例相同 k%=18.15%

5

下用正六边形求解矩形区域覆盖问题

二 以正六边形形为单位的对矩形区域进行覆盖的模型II

（1） 模型的知识准备

在满足完全覆盖矩形区域的条件下，使得所用圆个数最少，就要充分利用每个圆覆盖的区域范围，尽可能减小重叠部分。为便于讨论，考虑三个圆相交的情况，如图1（a ）中以o1,o2,o3为圆心的圆，我们的目标是要使得他们之间相互重合部分面积达到最小，又从图1（b ）可以看出三圆重叠的面积比1（a ）中更小。

图1（a ） 图1（b ） 定理1：如果三个半径相同的圆两两相交且覆盖面积最大，则三圆必交于一点。

定理2：如果三圆两两相交于一点并且三个圆心围成等边三角形，则

其覆盖面积最大。

6