资源描述：
《求一个包含点集所有点的最小圆的算法_汪卫》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ISSN1000-9825JournalofSoftware软件学报2000,11(9):1237～1240X求一个包含点集所有点的最小圆的算法123汪卫王文平汪嘉业1(复旦大学计算机系上海200433)2(香港大学计算机系香港)3(山东大学计算机系济南250100)E-mail:weiwang1@fudan.edu.cn/jywangz@yahoo.com摘要提出一种算法,以解决求一个最小圆包含给定点集所有点的问题.证明了这种算法的时间复杂性为O(ûlg(d/R)û*n),其中R是所求的最小圆的半径,d为点集中不在圆周上但距圆
2、周最近的点到圆周的距离.关键词最小圆,计算几何.中图法分类号TP301求一个最小圆包含给定点集所有点的问题是人们在实践和理论上都十分感兴趣的一个问题.由于这个圆的圆心是到点集中最远点最近的一个点,因而在规划某些设施时很有实用价值.这个圆心也可看成是点集的中心.此外,在图形学中,圆也常可取作边界盒,使用它可减少很多不必要的计算.在空间数据库中可将该问题用于建立空间数据的索引以提高查询速度[1,2].这个问题看起来十分简单,但用直观的算法去解此问题,其复杂性可达O(n4),[3～5]其中n为点集中点的数目.有关此问题的讨论在计算几何
3、的专著及论文中未见报道.本文提出了一种新的算法并证明了这种算法的时间复杂性为O(ûlg(d/R)û*n),其中R是所求的最小圆的半径,d为点集中不在圆周上但距圆周最近的点到圆周的距离.1算法第1步.在点集中任取3点A,B,C.第2步.作一个包含A,B,C三点的最小圆.圆周可能通过这3点(如图1所示),也可能只通过其中两点,但包含第3点.后一种情况圆周上的两点一定是位于圆的一条直径的两端.第3步.在点集中找出距离第2步所建圆圆心最远的点D.若D点已在圆内或圆周上,则该圆即为所求的圆,算法结束.否则,执行第4步.第4步.在A,B,C
4、,D中选3个点,使由它们生成的一个包含这4点的圆为最小.这3点成为新的A,B和C,返回执行第2步.若在第4步生成的圆的圆周只通过A,B,C,D中的两点,则圆周上的两点取成新的A和B,从另两点中任取一点作为新的C.2算法正确性本节要证明上述算法一定能终止,且最后一次求得的圆即是所要求的包含点集所有点的最小圆.引理1.算法第4步所生成的圆的半径随着迭代过程递增.证明:因为第4步每一次生成的圆是包含原来的A,B,C三点,又要加上圆外的一点,而上一次生成的圆是包X本文研究得到国家自然科学基金(No.69973028)资助.作者汪卫,19
5、70年生,博士,讲师,主要研究领域为计算几何,数据库.王文平,1963年生,博士,副教授,博士生导师,主要研究领域为计算机图形学,计算几何,CAGD.汪嘉业,1937年生,教授,博士生导师,主要研究领域为计算机图形学,计算几何,CAGD.本文通讯联系人:汪嘉业,济南250100,山东大学计算机系本文2000-02-28收到原稿,2000-05-12收到修改稿—1238—JournalofSoftware软件学报2000,11(9)含A,B,C的最小圆,因而新圆的半径一定比原来的圆半径要大.□定理1.上述算法是收敛的,且最后得到包
6、含点集所有点的最小圆.证明:因为在点集中任取3点或两点生成的包含这3点或两点的最小圆的个数是有限的.由引理1可知,算法进行过程中所生成的圆的半径是递增的,因而经过有限次迭代后,可求得这些最小圆中半径最大的一个.从算法第3步可知,只有当点集中所有点都在由3个点或两个点生成的最小圆内时,算法才结束,因而最后得到的圆一定是包含点集中所有点的最小圆.□3时间复杂性我们用R表示包含点集所有点的最小圆的半径,用ri表示本文的算法迭代第i次所得到的最小圆的半径,Oi表示其圆心.设A,B,C是算法第i次迭代后所求得的3个点.D是点集中距它们所生
7、成的最小圆的圆心最远的点(如图2所示).不失一般性,以后假设C点和D点在AB连线的同侧.引理2.在ûOiDû和ri不变的情况下,当A和B位于圆的直径两端,且OiD⊥AB时,包含A,B,C,D四点的最小圆的半径为最小.证明:A,B,C三点不能同时位于一段小于180°的弧上,否则,此时最小圆应是其中两点连线为直径的圆.第3点在圆内.设AB连线不是Oi圆的直径(如图3所示).假设AB′是Oi圆的直径.因为B只能和D处于AB′的不同侧,因而包含ABD的最小圆一定包含B′,但包含AB′D的最小圆可以不包含B,因而,包含ABD的最小圆的半径
8、只能大于或等于包含AB′D的最小圆的半径.故而为了找到最小圆半径最短的情况,我们只要讨论AB是Oi圆直径的情况.设图4中A1B1是Oi圆的另一直径,包含A1,B1,D的最小圆的圆心为F,包含A,B,D最小圆的圆心为E.它们的半径分别为R2=DF=A1F,R1=D
