Warehouse Location 最小包围球

Posted on 2010-07-01 09:56 王之昊 阅读(962) 评论(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经过的点,那么这个球也就唯一确定了。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊