加载中…
个人资料
东方射日
东方射日
  • 博客等级:
  • 博客积分:0
  • 博客访问:43,405
  • 关注人气:18
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

最小包容圆的算法(二)

(2009-11-12 16:20:54)
标签:

最小包容圆

算法

几何

it

分类: 技术讨论


Applet算法

该算法是Pr. Chrystal (1885). 提出的

首先我们观察到MEC完全是由点集中的凸包(Convex Hull所决定的。MEC上的点总在凸包上。

算法的第一步就是以O(nlogn)复杂度计算凸包。我们称之为凸包H和凸包上的顶点h。下一步是取凸包上的任一边SS两边的顶点分别为h0h1。然后执行以下主循环:

算法主循环

  1. 对除S上的两点外的所有凸包顶点h,计算角度h0-h`-h1,假设所有角度中最小的角对应顶点v,角度值为α (alpha).
    • α  ≥  90
      • MEC是以S为直径的圆
    • α < 90
      • 继续下面步骤2
  1. 检查三角形 h0-h`-h1中的其他角
    • 如没有钝角
      • h0-h`-h1决定的圆就是MEC
  2. 如果有一个角是钝角,则取钝角对面的边为S,重复步骤1

 

分析

首先计算凸包的复杂度是O(nlogn),算法主循环次数则和凸包上的点线性相关。最糟糕情况下,主循环可能对凸包的所有对角线运算一次。凸包中对角线的数量则和凸包上的点成平方关系。所以最终的算法复杂度是O(nlogn)加上O(n’^3)n’是凸包上的点的个数

看起来是n^3的复杂度,但是在执行中运行时间非常依赖于开始运算所选择的边,实际运算中,这个算法能提供相当好的性能

这里还需要证明上述算法能够找到MEC。可以看到循环的每一次迭代,算法返回一个半径小一点的圆并且保证所有的点仍旧包容在说返回的圆内。这样,最终返回的圆就是MEC

 

线性时间复杂度的算法



Nimrod Megiddo使用剪裁-搜索的方法,提出了一个复杂度为O(n)的寻找MEC的算法。


剪裁-搜索

Megiddo的算法的核心是剪裁-搜索。在一个剪裁-搜索的算法中,每一次迭代将搜索范围缩小到一个固定的比例f,最终的复杂度是 O(n)*(1 (1-f) (1-f)2 ...),这个等比数列是收敛的,最终结果是一个常数,这样我们就得到一个时间复杂度是O(n)的结果。


例如,假设每次迭代我们可以将搜索范围缩小1/4,那么我们重复这一过程,我们最终可以将搜索范围缩小到我们说需要的结果,例如n≤3的时候,剩余的3个对象就是我们所需要的最终结果。在这种情况下,总的时间是(n 3n/4 9n/16 ...),很容易知道这个等比数列的极限是4n。这样我们知道这个算法的时间复杂度就是和n成线性关系的O(n)

利用等比数列来将算法复杂度降低到线性的思路是Megiddo提出的。在此之前这已经被用在O(n)median-finding算法中。不过,是Megiddo第一个将这个方法大量用在计算几何的许多基本的问题上。


Megiddo的线性时间复杂度的算法

在这个寻找MEC的过程中,每一次迭代,Megiddo的算法将至少剔除1/16的点。即每次迭代,本算法将至少找出1/16的点可以从点集S中移除并不影响最后的结果。这个过程可以一直进行直到最终该过程结束,例如只剩下3个点。该算法的复杂度是(n 15n/16 225n/256 ...) 16n.


要剔除1/16的点,需要一些技巧,在本算法中,下面两个子过程被大量使用:

  • median(S, >)
    • 取一组点的集合S,确定一个两两比较的方式,返回集合的中位数
  • MEC-center(S, L)
    • 取一组点的集合S和一条线L,确定MEC的圆心将落在S的哪一边。

在上面我们提到,在Megiddo之前,median()已经有了一个线性复杂度的算法,MEC-center()的算法在他一篇1983年的论文上发表过。这两个算法的详细介绍不在本文讨论中,不过这两个都是使用剪裁-搜索的算法,复杂度均为线性。其中MEC-center()的算法就是整个算法的一个简化版本。


在上述基础上,每次迭代剔除1/16的点的算法描述如下:

  • 将点集中的n个点任意分为n/2个点的两个部分
  • 对每一对点构造一条中垂线,这样我们得到n/2条线
  • 计算上述斜率并调用median()找出斜率为中位数的线,我们称此斜率为Mmid.
  • 将斜率大于等于Mmid的线和小于Mmid的线两两建立对应关系,我们可以得到n/4个交点。我们将这个点集称为I
  • 在点集I中调用median()找出y值为中位数的点,该y值称之为Ymid.
  • 调用MEC-center()找出在MEC的圆心落于直线y=Ymid的那一边,在这里不失一般性,我们假设MEC的圆心C落在该直线的上面
  • Iy值小于Ymid的点称为子集I’ (I’包含n/8个点.)
  • 构造一条直线L,将I’中的点平分为左右两半
  • L调用MEC-center(),不失一般性,假设MEC的圆心C落在L的右边
  • L左边的点归为子集I’’I’’包含n/16个点


现在,对于上述I''n/16个交点中的每一个,我们可以提出在S中的一个点。原因如下:


在两次调用MEC-center()后,我们确定MEC的圆心C必然位于的ymid上方和L的右边。而I''中的点都位于Ymid的下方和L的右边。

I''中的每个点都是两条中垂线的交点,其中有一条线的斜率大于等于Mmid,这样该线比然不会经过我们所知的C所位于的象限。我们称该中垂线为B,这样我们容易知道C位于B的哪一边,这样我们在构造B的两点中,我们称Pc是那个和C位于同一边的点,另一个点我们称之为Px


这样很容易证明PcC的距离小于Px,因此Pc不可能位于MEC上,这样我们可以安全剔除Pc


这两步我们可以就I''中的每个点剔除一个S中的点,总共剔除了n/16个点。


这里,有可能存在一些特殊的情形,例如中垂线平行或有多点共线等。就这些退化的情形我们不展开讨论,但即使在这些情况下,该算法仍旧可以保证同样的性能。事实上,在上述这些退化的情况下,该算法的一次迭代能够剔除更多的点。简而言之,Megiddo的算法保证每次迭代能够剔除至少1/16个输入的点。


这样,Megiddo的算法能够在线性复杂度内得到MEC

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有