平面点集的最小包围圆算法设计及实现.pdf

华北计算技术研究所 平面点集的虽小包围圆 计算几何大作业 平面点集的最小包围圆算法设计 及实现 王立（P1016017 ） 张涵初（P1016015 ） 张超（P1016005 ） 华北计算技术研究所 一、问题背景 欲在一平面区域内建立一个固定的无线信号收发中转基站，平面区域内有若干个固定的 无线通信用户（可抽象为平面内一点）。各无线通信用户之间若要实现互联通信，均需要无 线通信用户先与中转基站建立无线链接，再通过中转基站链接区域内任一点。那么这个无线 信号中转基站应该选在哪里呢？根据直觉，应该选在中转基站射频作用距离范围的“中心”。 准确地讲，也就是包围这些点的那个最小圆的圆心——该位置的好处是，中转基站与它射频 作用范围内的点实现通信时，射频发射机的发射功率即功耗达到最小化（无线射频通信中， 作用距离越短，射频发射机功耗越小）。于是可抽象出如下问题：给定由平面上n 个点所组 成的一个集合P （对应于中转基站射频作用范围覆盖的区域内的通信用户），试找出P 的最 小包围圆（smallest enclosing disc ），即包含P 中所有点并且半径最小的那个圆。可以证明， 这个最小包围圆有且仅有一个。 二、实验内容 本实验主要完成了平面上随机点集P的生成和关于P的最小包围圆的计算。在生成平面 随机点集时，通过伪随机函数rand()函数实现了在平面矩形区域、平面圆形区域以及平面环 形区域内的均匀随机分布。在计算最小包围圆的过程中，使用并改进了一种比较高效的线性 算法，在O(n) 的时间内计算出了覆盖平面点集P的最小圆。 生成平面随机点集P时，我们将点的分布区域设置为平面矩形、圆形和扇形等，并将上 述算法分别作用到不同分布区域的平面点集P，对比分析了其各自时间复杂度。 1 华北计算技术研究所 平面点集的虽小包围圆 计算几何大作业 三、算法的理论描述 在我们熟悉的二维平面的线性规划问题中，在目标函数和给定的初始边界条件共同确定 出最优顶点P时，若引进一张半平面 ，顶点P落在 所包围的区域内，则当前的最优点可以 1 1 保存前一次所求出的最优顶点P而不必修改。将此思路应用于最小外接圆算法：对于由平面 点集P 内的多个点 ， ，… … ， （相当于i个初始边界条件）确定出一个最小包围圆 , 1 2 如果引入一张新的半平面 ，此半平面为以 的圆心 为圆心，以平面上不包含于P的一点 +1 | | 与 的圆心 的距离 为半径。只要此前的最优解顶点（即唯一确定最小包围圆的 +1 +1 几个关键顶点）能够包含于半平面+1 中，则不必对此最优解进行修改，亦即此亦为新点集 的最优解；否则，新的最优解顶点必然位于这个新的半空间的边界上。其形式如图 1 所示： 图1——若 ∈ ，则 = ，若 ∉ ，则 更新 −1 −1