简介:IncrementalalgorithmisoneofthemostpopularproceduresforconstructingDelaunaytriangulations(DTs).However,thepointinsertionsequencehasagreatimpactontheamountofworkneededfortheconstructionofDTs.Itaffectsthetimeforbothpointlocationandstructureupdate,andhencetheoverallcomputationaltimeofthetriangulationalgorithm.Inthispaper,asimpledeterministicinsertionsequenceisproposedbasedonthebreadth-first-searchonaKd-treewithsomeminormodificationsforbetterper-formance.Usingparentnodesassearch-hints,theproposedinsertionsequenceprovestobefasterandmorestablethantheHilbertcurveorderandbiasedrandomizedinsertionorder(BRIO),especiallyfornon-uniformpointdistributionsoverawiderangeofbenchmarkexamples.