A sweepline algorithm for voronoi diagram

Algorithmica(1987)2:153-174Algorithmica91987Springer-VerlagNewYorkInc.ASweeplineAlgorithmforVoronoiDiagramsStevenFortune~Abstract.WeintroduceageometrictransformationthatallowsVoronoidiagramstobecomputedusingasweeplinetechnique.ThetransformationisusedtoobtainsimplealgorithmsforcomputingtheVoronoidiagramofpointsites,oflinesegmentsites,andofweightedpointsites.AllalgorithmshaveO(nlogn)worst-caserunningtimeanduseO(n)space.KeyWords.Voronidiagram,Delaunaytriangulation,Sweeplinealgorithm.1.Introduction.TheVoronoidiagramofasetofsitesintheplanepartitionstheplaneintoregions,calledVoronoiregions,onetoasite.TheVoronoiregionofasitesisthesetofpointsintheplaneforwhichsistheclosestsiteamongallthesites.TheVor0noidiagramhasmanyapplicationsindiversefields.Oneapplicationissolvingclosest-sitequeries.Supposewehaveafixedsetofsitesandaquerypoint,andwouldliketoknowtheclosestsitetothequerypoint.IftheVoronoidiagramofthesetofsitesisconstructed,thenthisproblemhasbeenreducedtodeterminingtheregioncontainingthequerypoint.Ifinfactthenumberofquerypointsislargerelativetothenumberofsites,thentheconstructionoftheVoronoidiagramisworthwhile.ThepapersbyPreparata[16]andbyGreenandSibson[8]containreferencestootherapplications.WepresentsimplesweeplinealgorithmsfortheconstructionofVoronoidiagramswhensitesarepointsandwhensitesarelinesegments.Theproposedalgorithmsarebasedonthesweeplinetechnique[17],[20].Thesweeplinetechniqueconceptuallysweepsahorizontallineupwardacrosstheplane,notingtheregionsintersectedbythelineasthelinemoves.ComputingtheVoronoidiagramdirectlywithasweeplinetechniqueisdifficult,becausetheVoronoiregionofasitemaybeintersectedbythesweeplinelongbeforethesiteitselfisintersectedbythesweepline.RatherthancomputetheVoronoidiagram,wecomputeageometrictransformationofit.ThetransformedVoronoidiagramhasthepropertythatthelowestpointofthetransformedVoronoiregionofasiteappearsatthesiteitself.ThusthesweeplinealgorithmneedconsidertheVoronoiregionofasiteonlywhenthesitehasbeenintersectedbythesweepline.ItturnsouttobeeasytoreconstructtherealVoronoidiagramfromitstransformation;infactinpracticetherealVoronoidiagramwouldbeconstructed,andthetransformationcomputedonlyasnecessary.ThesweeplinealgorithmscomputetheVoronoidiagramofnsitesintimeO(nlogn)andspaceusageO(n).AT&TBellLaboratories,MurrayHill,NJ07974,USA.ReceivedApril6,1986;revised12October,1986.CommunicatedbyBernardChazelle,154S.FortunePreviousalgorithmsforVoronoidiagramsfallintotwocategories.Firstareincrementalalgorithms,whichconstructtheVoronoidiagrambyaddingasiteatatime.Thesealgorithmsarerelativelysimple,buthaveworst-casetimecomplexityO(n2).However,thealgorithmsmayhavegoodexpectedtimebehavior[2],[8],[15].Thesecondcategoryofalgorithmsaredivide-and-conqueralgorithms.Thesetofsitesissplitintotwoparts,theVoronoidiagramofeachpartcomputedrecursively,andthenthetwoVoronoidiagramsmergedtogether.Ifthesitesarepoints,thentheycanbesplitsimplybydrawingalinethatseparatesthesitesintohalves[18].Ifthesitesarelinesegments,thenmorecomplexpartitioningisnecessary[21].Withcare,thedivide-and-conqueralgorithmscanbeimple-mentedinworst-casetimeO(nlogn).Thedifficultyofthedivide-and-conqueralgorithmsisgenerallywiththemergestepthatcombinestwoVoronoidiagramstogether.Whilethetimerequiredforthisstepisonlylinearinthenumberofsites,thedetailsofthemergearecomplexandhardtoimplement.Thesweeplinealgorithmspresentedinthispaperarecompetitiveinsimplicitywiththeincrementalalgorithms.Sincetheyavoidthemergestep,theyaremuchsimplertoimplementthanthedivide-and-conqueralgorithms.Buttheyhavethesameworst-casetimecomplexityasthedivide-and-conqueralgorithms.WealsopresentanalgorithmtocomputetheVoronoidiagramofweightedpointsites,inwhicheachsitehasanadditiveweightassociatedwithit.Thealgorithmusesexactlythesamesweeplinetechnique,andhastimecomplexityO(nlogn).ThebestpreviouslyknownalgorithmforthisproblemhastimecomplexityO(nlog2n).Thealgorithmsinthispaperdonotassumethatthepointsareingeneralposition.Thussitescanbearbitrarilycollinearorcocircular.Inordertoprovethatthealgorithmsarecorrect,evenwithdegeneracies,weassumethatarithmeticisperformedexactly.Aninterestingproblemistoshowthatthealgorithmsperformcorrectlyinmorereasonablemodelsofcomputerfloating-pointarith-metic.Thealgorithmforthecaseofpointsiteshasbeenimplemented;therearenoknownexamplesthatcauseittofail.2.PointSites.Wefirstconsiderthecasethatallsitesarepointsintheplane.Thissimplecasehasbeendiscussedextensivelyintheliterature.Wesummarizethedefinitionsandelementarypropertiesbelow;formoredetails,see,forexample,[18]or[11].Foramoregeneralsituationthanpointsites,see[14].IfpcR2,thenPxandpyarethex-andy-coordinatesofp,respectively.Pointsp,q~R2arelexicographicallyordered,pq,if/~vqyorpy=qyandPxq~.Alineorsegmentlisbelowp~R2ifthereisapointq~lwithp~=qxandqyp~.Forp,q~R2,e(p,q)istheEuclideandistancebetweenpandq.LetSbeasetofnpointsintheplane,calledsites.ForpcS,dp:R2-~Risthe(Euclidean)distancefromapointinR2top,andd:R2-~Risminp~sdp.TheVoronoicircleatz~R2isthecirclecenteredatzofradiusd(z).ThebisectorBpqofp,q~Sis{zcR2:d~(z)=dq(z)};Bp