麻省理工大学算法导论lecture12

《麻省理工大学算法导论lecture12》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoAlgorithms6.046J/18.401J/SMA5503Lecture12Prof.ErikDemaineComputationalgeometryAlgorithmsforsolving“geometricproblems”in2Dandhigher.Fundamentalobjects:pointlinesegmentlineBasicstructures:pointsetpolygon©2001byErikD.DemaineIntroductiontoAlgorithmsDay21L12

2、.2ComputationalgeometryAlgorithmsforsolving“geometricproblems”in2Dandhigher.Fundamentalobjects:pointlinesegmentlineBasicstructures:triangulationconvexhull©2001byErikD.DemaineIntroductiontoAlgorithmsDay21L12.3OrthogonalrangesearchingInput:npointsinddimensions•E.g.,rep

3、resentingadatabaseofnrecordseachwithdnumericfieldsQuery:Axis-alignedbox(in2D,arectangle)•Reportonthepointsinsidethebox:•Arethereanypoints?•Howmanyarethere?•Listthepoints.©2001byErikD.DemaineIntroductiontoAlgorithmsDay21L12.4OrthogonalrangesearchingInput:npointsinddim

4、ensionsQuery:Axis-alignedbox(in2D,arectangle)•ReportonthepointsinsidetheboxGoal:Preprocesspointsintoadatastructuretosupportfastqueries•Primarygoal:Staticdatastructure•In1D,wewillalsoobtainadynamicdatastructuresupportinginsertanddelete©2001byErikD.DemaineIntroductiont

5、oAlgorithmsDay21L12.51DrangesearchingIn1D,thequeryisaninterval:Firstsolutionusingideasweknow:•Intervaltrees•Representeachpointxbytheinterval[x,x].•ObtainadynamicstructurethatcanlistkanswersinaqueryinO(klgn)time.©2001byErikD.DemaineIntroductiontoAlgorithmsDay21L12.61D

6、rangesearchingIn1D,thequeryisaninterval:Secondsolutionusingideasweknow:•Sortthepointsandstoretheminanarray•Solvequerybybinarysearchonendpoints.•ObtainastaticstructurethatcanlistkanswersinaqueryinO(k+lgn)time.Goal:ObtainadynamicstructurethatcanlistkanswersinaqueryinO(

7、k+lgn)time.©2001byErikD.DemaineIntroductiontoAlgorithmsDay21L12.71DrangesearchingIn1D,thequeryisaninterval:Newsolutionthatextendstohigherdimensions:•Balancedbinarysearchtree•Neworganizationprinciple:Storepointsintheleavesofthetree.•Internalnodesstorecopiesoftheleaves

8、tosatisfybinarysearchproperty:•Nodexstoresinkey[x]themaximumkeyofanyleafintheleftsubtreeofx.©2001byErikD.DemaineIntroductiontoAlgor