资源描述：
《Voronoi_Diagram_Notes_1》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、containsqchangesasaresultoftheithinsertion.LetPidenotethisprobability(wheretheprobabilityistakenoverrandominsertionorders,irrespectiveofthechoiceofq).Sinceqcouldfallthroughuptothreelevelsinthesearchtreeasaresultofeachtheinsertion,theexpectedlengthofqssearchpathinthefinalstructureisatm
2、ostn3Pi.i=1WewillshowthatPi≤4/i.Fromthisitwillfollowthattheexpectedpathlengthisatmostn4n13=12,iii=1i=1whichisroughly12lnn=O(logn)bytheHarmonicseries.ToshowthatPi≤4/i,weapplyabackwardsanalysis.Inparticular,considerthetrapezoidthatcontainsqaftertheithinsertion.Recallfromlasttimethat
3、thistrapezoidisdependentonatmostfoursegments,whichdefinethetopandbottomedges,andtheleftandrightsidesofthetrapezoid.Sinceeachsegmentisequallylikelytobethelastsegmenttohavebeenadded,theprobabilitythatthelastinsertioncausedqtobelongtoanewtrapezoidisatmost4/i.Thiscompletestheproof.Guarant
4、eesonSearchTime:Oneshortcomingwiththisanalysisisthateventhoughthesearchtimeisprovablysmallintheexpectedcaseforagivenquerypoint,itmightstillbethecasethatoncethedatastructurehasbeenconstructedthereisasingleverylongpathinthesearchstructure,andtheuserrepeatedlyperformsqueriesalongthispat
5、h.Hence,theanalysisprovidesnoguaranteesontherunningtimeofallqueries.Althoughwewillnotproveit,thebookpresentsastrongerresult,namelythatthelengthofthemaximumsearchpathisalsoO(logn)withhighprobability.Inparticular,theyprovethefollowing.Lemma:Givenasetofnnon-crossinglinesegmentsintheplan
6、e,andaparameterλ>0,theprobabilitythatthetotaldepthoftherandomizedsearchstructureexceeds3λln(n+1),isatmost2/(n+1)λln1.25−3.Forexample,forλ=20,theprobabilitythatthesearchpathexceeds60ln(n+1)isatmost2/(n+1)1.5.(Theconstantfactorshereareratherweak,butamorecarefulanalysisleadstoabetterbou
7、nd.)Nonetheless,thisitselfisenoughtoleadtovariantofthealgorithmforwhichO(logn)timeisguaranteed.Ratherthanjustrunningthealgorithmonceandtakingwhatitgives,insteadkeeprunningitandcheckingthestructuresdepth.Assoonasthedepthisatmostclognforsomesuitablychosenc,thenstophere.Dependingoncandn
8、,theabovelem
