Posted on 2010-07-01 09:56
王之昊 阅读(1000)
评论(0) 编辑 收藏 引用 所属分类:
三维几何 、
随机增量
Warehouse Location
最小包围球，采用随机增量的方法。时间复杂度O(n)。
首先一个点的情况最小包围球的半径为0，没有什么意义。
对于求 n 个点的最小包围球，假设这 n 个点分别为 p1,p2, ..,pn。我们可以先求两个点p1,p2的最小包围球，再求三个点p1,p2,p3的最小包围球，总之在求前 k 个点的最小包围球之前，先求前 k-1 个点的最小包围球。这里的点是已经经过随机洗牌的，假设前k个点的最小包围球是Ck
如果pn被 球Cn-1 所包围，那么Cn=Cn-1；否则Cn一定经过pn，这样我们知道Cn经过的一个点，我们再重复上面的方法重新去算一遍Cn，结果要么是直接确定了Cn，要么是增加一个Cn一定经过的点。然而如果知道4个Cn经过的点，那么这个球也就唯一确定了。