求一个包含点集所有点的最小圆的算法_汪卫

ISSN1000-9825JournalofSoftware2000,11(9):12371240X汪卫1　王文平2　汪嘉业31(200433)2()3(250100)E-mail:[e-mail]/[e-mail]提出一种算法,以解决求一个最小圆包含给定点集所有点的问题.证明了这种算法的时间复杂性为O(ûlg(d/R)û*n),其中R是所求的最小圆的半径,d为点集中不在圆周上但距圆周最近的点到圆周的距离.最小圆,计算几何.TP301.,..,,,.[1,2].,,O(n4),n.[35].O(ûlg(d/R)û*n),R,d.11.3A,B,C.2.A,B,C.3(1),,3..3.2D.D,,.,4.4.A,B,C,D3,4.3A,BC,2.4A,B,C,D,AB,C.2,.1.4.证明:4A,B,C,,X(No.69973028).,1970,,,,.,1963,,,,,,CAGD.,1937,,,,,CAGD.:,250100,2000-02-28,2000-05-12A,B,C,.1.,.证明:33.1,,,.3,3,,.3R,rii,Oi.A,B,Ci3.D(2).,CDAB.2.ûOiDûri,AB,OiDAB,A,B,C,D.证明:A,B,C180,,.3.ABOi(3).ABOi.BDAB,ABDB,ABDB,,ABDABD.,ABOi.4A1B1Oi,A1,B1,DF,A,B,DE.R2=DF=A1F,R1=DE=AE.DB1A190,B1B1,A1,D,FOiAi=90.DB1A190,B1B1,A1,D,,DFA1OiFB1D,FOiA1=DB1A1,FOiA190.FOiA1ûOiFû2ûA1Fû2-ûOiA1û2,ûOiFûR22-r2i.(1)OiEAûOiEûR21-r2i,OiFDûOiFû+ûDFûûOiEû+ûEDû,R2+R22-r2iR1+R21-r2i.(2)(2)R2R1.2.2,A,B,CAB,C,.3.,:1238JournalofSoftware　软件学报　2000,11(9)ri+1-ri(1-Q)(R-ri),0Q1.(3)证明:2,ABOiDAB(5).A,B,DE,ri+1=ûEDû=ûEAû=ûEBû.OiEAûOiEû2=ûAEû2-ûOiAû2,(ûODû-ri+1)2=r2i+1-r2i.ri+1=ûODû2+r2i2ûODû,ri+1-ri=(ûODû-ri)22ûODû.Oi,2RûOiDûRri,ri+1-ri(R-ri)24RR+ri4R(R-ri)(1-Q)(R-ri),0Q1.,Q0,0Q01QQ0.4.iri,:ûR-riû(Q0)iR.(4)证明:(3)ûR-ri+1ûQ0ûR-riû,ûR-riûQ0ûR-ri-1û...(Q0)iûR-r0û(Q0)iR.d.5.j,rj=R,rj-1rj,:R-rj-1d28R.(5)证明:26,rj,R-rj-1,d.6,(5),(5).E=ûOj-1Ojû,rj-1=ûOjAû2-ûOjOj-1û2=R2-E2,R-rj-1=R-R2-E2.(6)d=R+E-rj-1=R+E-R2-E2,E2+(R-d)E+12(d2-2Rd)=0,E=-(R-d)+(R-d)2-2d2+4Rd2=-(R-d)+R2-d2+2Rd2d-R+R22=d2.(6)Taylor,R-rj-1=R-R1-12ER2-14ER41-HER2.0H1,1239汪卫等:求一个包含点集所有点的最小圆的算法　　　　　　　　　　　　　　　　　　　　　　　　　　　R-rj-1R2ER2=E22Rd28R.2.Olgd8Rn,n.证明:j,rj=R,rj-1rj.(5)R-rj-1d28R.,rj-1rj=R.(4),i,(Q0)iRd28R,(7)ûR-riûd28R.,.(7),lgd8RlgQ0+2=Olgd8R,[x]x.O(n),Olgd8Rn.1SametH.TheDesignandAnalysisofSpatialDataStructure.NewYork:Addison-WesleyPublishingCompany,19892SametH.ApplicationofSpatialDataStructure.NewYork:Addison-WesleyPublishingCompany,19893O'RourkeJ.ComputationalGeometryinC.NewYork:CambridgeUniversityPress,19944PreparataFP,ShamosMI.ComputationalGeometryanIntroduction.NewYork:Springer-Verlag,19855ToussaintGT.ComputationalGeometry.Amsterdam,NewYork,Oxford:North-Holland,1985AnAlgorithmforFindingtheSmallestCircleContainingallPointsinaGivenPointSetWANGWei1WANGWen-ping2WANGJia-ye31(DepartmentofComputerScienceFudanUniversityShanghai200433)2(DepartmentofComputerScienceTheUniversityofHongKongHongKong)3(DepartmentofComputerScienceShandongUniversityJi'nan250100)AbstractToseekasmallestcirclecontainingallthepointofagivenpointsetisaninterestingprobleminbothpracticeandtheory.Inthispaper,analgorithmoffindingasmallestcirclecontainingallthepointsgivenispresented.ThetimecomplexityofthealgorithmisO(ûlg(d/R)û*n),whereRistheradiusbetweenthesmallestcircle,disthesmallestdistancebetweenthepointsofthesetthatarenotonthecircleandthecircle.KeywordsSmallestcircle,computationalgeometry.1240JournalofSoftware　软件学报　2000,11(9)