计算几何的问题

来自第三届全国研究生数学建模竞赛"Ad Hoc网络中的区域划分和资源分配问题"

要求用半径相等的圆来覆盖特定区域，使得所需圆个数最少，并满足两个条件：完全覆盖正方形区域和相邻两圆有大于百分比为k(k=5,18)的公共面积。
本问重点在于研究使用四边形、六边形覆盖的合理性、最优性。要求论证严密，模型正确，结果准确。
用圆有交叠地覆盖平面的一般方法，是用一系列正多边形完整覆盖平面，用正多边形的外接圆作为覆盖圆。要求覆盖圆数目最少，就要重叠的面积尽量少，从而要求正多边形不重叠，理论上可以证明，这样的正多边形仅有正六边形、正方形和正三角形三种。为了达到覆盖圆数目最小，各圆的公共面积应尽量小，但要分别大于所给的5%和18%两个要求，因而应分别使用正六边形和正方形覆盖。
对所给数据，容易计算，使用正六边形覆盖时，需要的最少圆数为45，18%时，一般计算得到64个圆。此结果可以进一步优化，比如改变覆盖正方形与题给正方形的相对角度、容许少量区域不被覆盖等。优化后，60个圆是比较好的结果。无论如何，所给出的结果，应有具体的覆盖方案佐证（图示）。
信道分配要求有公共部分的圆拥有不同的信道，这实质上是个着色问题。对于相交面积大于圆面积5%和18%的两种情形，分别需要3个和2个信道。
关于抗毁性的讨论，主要使用模拟方法。
对六边形覆盖方式，得到的结论是：当抽取2%的节点时，连通的概率大于0.99；当抽取5%的节点时，连通的概率大于0.98；当抽取10%的节点时，连通的概率大于0.96；当抽取15%的节点时，连通的概率大于0.92。
对正方形覆盖方式，得到的结论是：当抽取2%的节点时，连通的概率是0.99；当抽取5%的节点时，连通的概率是0.95；当抽取10%的节点时，连通的概率是0.875；当抽取15%的节点时，连通的概率是0.5620。
仿真结果说明，抽掉同样比例的节点六边形方式连通的概率比正方形覆盖大，正方形覆盖时随抽掉节点的比例增多连通性的概率下降很快。表面上看来，四边形重合面积大，连通性应该好，但事实恰好相反，原因在于，六边形覆盖时，在一个圆内有6个节点作为转发节点，与周围6个圆相邻，而在正方形覆盖时一个圆内有4个节点作为转发节点，与周