Two Algorithms for Constructing a Delaunay Triangulation.pdf

《Two Algorithms for Constructing a Delaunay Triangulation.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、InternationalJournalofComputerandInformationSciences,Vol.9,No.3,1980TwoAlgorithmsforConstructingaDelaunayTriangulation1D.T.Lee2andB.J.Schachter3ReceivedJuly1978;revisedFebruary1980ThispaperprovidesaunifieddiscussionoftheDelaunaytriangulation.Itsgeometricpropertiesarereviewedan

2、dseveralapplicationsarediscussed.TwoalgorithmsarepresentedforconstructingthetriangulationoveraplanarsetofNpoints.Thefirstalgorithmusesadivide-and-conquerapproach.ItrunsinO(NlogN)time,whichisasymptoticallyoptimal.ThesecondalgorithmisiterativeandrequiresO(N2)timeintheworstcase.H

3、owever,itsaveragecaseperformanceiscomparabletothatofthefirstalgorithm.KEYWORDS:Delaunaytriangulation;triangulation;divide-and-con-quer;Voronoitessellation;computationalgeometry;analysisofalgorithms.1.INTRODUCTIONInthispaperweconsidertheproblemoftriangulatingasetofpointsinthepl

4、ane.LetVbeasetofN~>3distinctpointsintheEuclideanplane.Weassumethatthesepointsarenotallcolinear.LetEbethesetof(n)straight-linesegments(edges)betweenverticesinV.Twoedgesel,e~~E,el~e~,willbesaidtoproperlyintersectiftheyintersectatapointotherthantheirendpoints.AtriangulationofVisa

5、planarstraight-linegraphG(V,E')forwhichE'isamaximalsubsetofEsuchthatnotwoedgesofE'properlyintersect.~16~1ThisworkwassupportedinpartbytheNationalScienceFoundationundergrantMCS-76-17321andtheJointServicesElectronicsProgramundercontractDAAB-07-72-0259.2NorthwesternUniversityDept.

6、ofElectricalEngineeringandComputerScience,Evanston,Illinois60201.aGeneralElectricCo.,P.O.Box2500,DaytonaBeach,Florida32015.2190091-703618010600-0219503.001091980PlenumPublishingCorporation220LeeandSchachterThereisnoconceptualdifficultyinvolvedinconstructingatriangulation.Anys

7、etofpointscanbetriangulatedifedgesareaddedwiththeprovisothatnonewedgeintersectsanexistingedge.WewillinvestigateaparticulartriangulationcalledtheDelaunaytriangulation.~)IthasthepropertythatthecircumcircleofanytriangleinthetriangulationcontainsnopointofVinitsinterior.Thispaperis

8、theresultofarecentstudywhoseobjectivewastodevelopanefficienta