|
参考：https://blog.csdn.net/commonc/article/details/52291822
https://blog.csdn.net/wu_tongtong/article/details/79362339
算法目的：最小圆覆盖算法可以在线性时间复杂度内求出覆盖n个点的最小圆
算法步骤：
①首先现将所有点随机排列
②按顺序把点一个一个的加入（一步一步的求前i个点的最小覆盖圆），每加入一个点就进入③
③如果发现当前i号点在当前的最小圆的外面，那么说明点i一定在前i个点的最小覆盖圆边界上，我们转到④来进一步确定这个圆，否则前i个点的最小覆盖圆与前i-1个点的最小覆盖圆是一样的，则不需要更新，返回②
④此时已经确认点i一定在前i个点的最小覆盖圆的边界上了，那么我们可以把当前圆的圆心设为第i个点，半径为0，然后重新把前i-1个点加入这个圆中（类似上面的步骤，只不过这次我们提前确定了点i在圆上，目的是一步一步求出包含点i的前j个点的最小覆盖圆），每加入一个点就进入⑤
⑤如果发现当前j号点在当前的最小圆的外面，那么说明点j也一定在前j个点（包括i）的最小覆盖圆边界上，我们转到⑥来再进一步确定这个圆，否则前j个点（包括i）的最小覆盖圆与前i-1个点（包括i）的最小覆盖圆是一样的，则不需要更新，返回④
⑥此时已经确认点i，j一定在前j个点（包括i）的最小覆盖圆的边界上了，那么我们可以把当前圆的圆心设为第i个点与第j的点连线的中点，半径为到这两个点的距离（就是找一个覆盖这两个点的最小圆），然后重新把前j-1个点加入这个圆中（还是类似上面的步骤，只不过这次我们提前确定了两个点在圆上，目的是求出包含点i，j的前k个点的最小覆盖圆），每加入一个点就进入⑦
⑦如果发现当前k号点在当前的最小圆的外面，那么说明点k也一定在前k个点（包括i，j）的最小覆盖圆边界上，我们不需要再进一步确定这个圆了（因为三个点能确定一个圆！），直接求出这三点共圆，否则前k个点（包括i，j）的最小覆盖圆与前k-1个点（包括i，j）的最小覆盖圆是一样的，则不需要更新。
时间复杂度：O(N)
空间复杂度：O(N)
复杂度证明：空间复杂度显然，下面来证时间复杂度
首先，因为我们已经将点打乱顺序，所以我们可以认为点是随机生成的
我们知道，当点完全随机时，第i个点在前i-1个点的最小覆盖圆外的几率是3/i（我们可以认为这个圆是由现在在边界上的那三个点来确定的，也就是说当随机生成的最后一个点不是那三个点时，新生成的点就在圆内，否则在圆外，所以第i个点在前i-1个点的最小覆盖圆外的概率只有3/i）
所以O(②)=∑i=1i≤n(i3iO(1)+3iO(④))O(②)=∑i=1i≤n(i3iO(1)+3iO(④))
而O(④)=∑i=1i≤n(i3iO(1)+3iO(⑥))O(④)=∑i=1i≤n(i3iO(1)+3iO(⑥)
易知O(⑥)=O(N)O(⑥)=O(N)
所以可以推出，这个做法是线性的
注意事项:
以上时间复杂度的证明全部基于点的排列随机，如果点的排列不随机，那么时间复杂度将有可能达到O(N3)O(N3)
所以最小圆覆盖算法只能在O(N)时间内求出N的点的最小覆盖圆，而不能在O(N)的时间内求出所有的前i个点的最小覆盖圆
例题：给定n个点求最小覆盖圆圆心及半径(BZOJ1336/1337) | 
转播
