[PDF] CMSC 754 Computational Geometry

In this course, our focus will be largely on problems in 2-dimensional space, with occasional forays into spaces of higher dimensions Because the field was

[PDF] Computational Geometry Exercise Set 8 HS10

Computational Geometry Exercise 1 Exercise 2 a1 3 http://www ti inf ethz ch/ew/courses/CG10/ 3 S1 a2 Exercise 3

[PDF] Computational Geometry Exercise Set 10 HS07

Computational Geometry http://www ti inf ethz ch/ew/courses/CG07/ Exercise 1 (10 points) k a1 S1, , ak Sk k O(n 2 n) k k Exercise 2 (10 points)

[PDF] Computational Geometry Lecture Notes HS 2013

These lecture notes are designed to accompany a course on “Computational Geometry” three hours of lecture and two hours of exercises each week

[PDF] 9 Computational Geometry Algorithms Library (CGAL)

The exercises below are intended to provide a means to test your understanding of the programming-related material covered in the course

[PDF] COMPUTATIONAL GEOMETRY INTRODUCTION

https://cw felk cvut cz/doku php/courses/a4m39vg/start What is Computational Geometry (CG)? CG Solves geometric problems that require clever

[PDF] Computational Geometry · Lecture Introduction & Convex Hulls

19 oct 2015 · Course Information Lecture Slides Exercises Additional Material Computational Geometry in Computer Science Master's Studies

[PDF] Computational Geometry

This course is about Computational geometry (theory): Study of geometric problems on geometric data, and how efficient algorithms that solve them can be

Computational Geometry - Some Easy

14 avr 2001 · Computational geometry is concerned with the algorithmic study of elemen- tary geometric problems Ever since its emergence as a new branch

[PDF] Graph-Theoretic Solutions to Computational Geometry Problems

algorithms to computational geometry 1 Geometric analogues of classical graph algorithm problems Typical issue: using geometric information

58795_6cmsc754_lects.pdf

CMSC754

ComputationalGeometry

DavidM.Mount

DepartmentofComputerScience

UniversityofMaryland

Spring2012

preparedbyDavidMountfor thecou rseCMSC754,Compu tationalGe ometry,attheUniversityof Maryla nd.Permiss iontouse,copy,modify,an d

distributethesenotesforeducationalpurpos esandwithoutfeeisherebygranted,providedthatthiscopyrightnoticeappearinall copies.

LectureNotes1CMSC754

Lecture1:IntroductiontoCom put ationalGeometry

WhatisCom putati onalGeometry?"Computationalgeometry"isat ermclaimedbyanumberof differentgroups. Theter mwascoinedperhapsfirs tbyMarvinMi nskyinhi sbook"Perceptrons",whichwasaboutpattern

recognition,andithasalsobeenuse doftentodescrib ealg orithmsformanip ulatingcu rvesandsurfacesinsolid

modeling.Its mostwidelyrecognizedus e,however, isto describethesubfieldof algorithmt heorythatinvol ves

thedesig nandanalysisofe fficientalgo rithmsforproblemsinvolvinggeometricinputand output. Thefield ofcomputationalgeomet ryde velopedrapidlyinthe late70' sandthroughthe8 0'sand90' s,andit

stillc ontinuestodevelop.Historically,c omp utationalgeometrydevelopedasa generalizationofthestudy of

algorithmsforsortingands earchingin1- dimensionalspacetoproblemsinvolvingmulti-dimensionalinputs. Becauseofits hist ory,thefieldofcomput ationalgeometryhasfocus edmostlyonproblems in2-dimensional

spaceandtoaless erextenti n3-di men sionalspace.Whenpr oblemsarec onsidered inmulti-dimensionalspaces,

itisu sually assumedthatthedimen sionofthespaceis asmallconstant(say,10orlower).Nonetheless,recent workinthis areah asconsidered alimitedset ofproblem sinveryhighdimens ionalspaces,par ticularlywith respecttoapproximation algo rithms.Inthiscourse,ourfocuswil lbelargelyonprobl emsin 2-dimensional space,withoccasional foraysinto spacesofhigherdimensions. Becausethefiel dwasdevel opedbyresearcher swhosetrai ningwasindiscretealgorithms(asopposedtonu- mericalanalysis)the fieldhasalsofocusedmore onthe discretenatureof geometricproblems( combinator ics andtopol ogy,inparticular), asopposedtocont inuousissues.Thefield primar ilydealswi thstraightorflat

objects(lines,l inesegments,polygons,planes,and polyhedra)orsimpl ecurv edobjectssuchascircles. Thisis

inc ontrast,say,tofieldssuch assolidmodeling ,wh ichfocusonissuesinvolvingcurvesandsurfacesandtheir representations. Therearemany fieldsofcomputers ciencethatdealwi thsolvingprobl emsofageometricnat ure.Thes eincl ude computergraphics ,computervisionandimageproces sing,robotics,computer-aideddesign andmanufacturing, computationalfluid-dynamics,andgeographi cinformationsystems,tonameafew .On eofthegoalsof com - putationalgeometryistopr ovidethebasic geometrictool sneededfr omwhichapplicationar eascanthenbui ld

theirprograms.T herehasbeensignifica ntprogressmadeto wardsthisgoal ,butitisst illfarf rombeingf ully

realized. ATypicalProbleminComputationalGeometry:Hereisanexample ofa typicalproblem, calledtheshortestpath problem.Givenasetpolygonalobstaclesintheplane,findtheshortestob stacle-avoidingpathfromsomegiven

startpoint toagivengoalp oint (see Fig.1).Althoughitispossibletoreducethisto ashortest pathproblemon

agraph(calledthevisibilitygraph,whichwewilldiscusslaterthissemester),andthenapplyanongeometric algorithmsuchasDijkstra' salgorithm, its eemsthatbysolvingthepr obleminit sgeometricdomainit should beposs ibletodevisemoreefficients olutions. Thisisoneofthemainrea sonsforth egrowthofinterestin geometricalgorithms. stst

Fig.1:Shortes tpat hproblem.

Themeasur eofthequalityof analgor ithmin computationalgeometryhastraditi onally beenitsasymptotic worst-caserunningtime.Thus,analgorithmrunninginO(n)timeis bette rthanonerunning inO(nlogn) timewh ichisbettertha non erunninginO(n 2 )time.(Thisp articularproble mcanbesolvedinO(n 2 logn) timeby afairlysimp lealg orithm,inO(nlogn)bya relat ivelycomplexalgorithm,anditcanbeapproximate d quitewellbyanal gorithmwhose running time isO(nlogn).)Inso meca sesaveragecaserunningtimeis

LectureNotes2CMSC754

consideredinstead.However ,formanytypesofgeometri cinputs(this oneforexample)itisdif ficultt odefine inputdistributionsth atarebotheasytoanalyzea ndrepresentativeoftypicalinputs.

StrengthsComputationalGeometry:

DevelopmentofGeometricTools :Priortocomputational geometry,ther eweremanyadhocsolutionstoge- ometriccomputationalproblems, someefficient,someineffi cient,andsomesi mplyi ncorrect.Because of itsemp hasisofmathematicalrigo r,compu tationalgeometryhasmadegreatstridesinestablishingcorrect, provablyefficientalgorithmics olutionstomanyof theseproblems. EmphasisonProvable Efficiency: Priortothedev elopmentofcomputati onalgeometryli ttlewasunders tood aboutthe computationalcompl exityofmanygeometriccompu tations.Forexample ,givenane ncodingof allthezi pcoderegions intheUSA,and given alatitudeandlongitudefromaGPSde vice,howlongshould ittak etocomputethe zipc odeassociatedwiththeloc ation?Howshouldthecomputation timedependon theamoun tofpreprocessingtimeand spacea vailable?Computationalgeometryputsuc hquestionsonthe firmgroundingof asymptoticcomplexi ty, andinsomecasesithasbeenpos si bletoprovethatalgorithms discoveredinthisareaareoptimal solutions. EmphasisonCorrectness/ Robust ness:Priortothedevelopmentofcomputationalgeometry,manyofthesoft- waresystem sthatweredevelopedwe retroubledby bugsarisingfr omtheconfluenceoftheconti nuous natureofgeometryand thedi scretenatureofcomput ation. Forexampl e,giventwoli nesegmentsint he plane,dothey inter sect?Thisproblemi sremarkablytrickytosolv esincetwolinese gmentsmayarise frommany differentconfigu rations:lyingonparallellines ,lyingonthesameline,touchingend-to-end, touchingasinaT-junction.S oftwaretha tis base dondiscretede cisionsinvolvingmillionsofsuch inter- sectiontestsmayve rywellfa ilifanyoneo fthesetestsisco mputederr oneously.Computationalgeometry researchhasputtherob ustandcorrec tcomputing ofgeom etricprimiti vesonasolidmathematical foun- dations. LinkagetoDis creteCombinatori alGeometry:Thest udyofnewsolutions tocomput ationalproblems has givenriset omanynewproblemsinthe mathematicalfield ofdiscretecombin atorialgeometry.Forex- ample,considera polygonboundedbynsidesintheplan e.S uchapo lygonmightbethoug htofasthe top-downviewofthewalls inanartgallery .Asafunc tionofn,howmany"guardingpoints"sufficesothat everypointwi thinthepolygonc anbeseenbyatleast oneoftheseguards.Such combinatorialquestions canha veprofoundimplicat ionsonthecomplexit yofalgorithms.

LimitationsofComputationalGeometry:

Emphasisondiscret egeometry: Therearesome fairlynat uralreasonswh ycomputationalgeometrymay neverfullyaddres stheneedsofalltheseappli cationsareas,an dtheselimitations shouldbeund erstood beforeundertakingthi scourse.Oneisthedis cretenatureofcomputationalgeometry.Therearemany applicationsinwhichobjectsare ofaverycont inuousnature:computat ionalphysics,computationalflui d dynamics,motionplanning. Emphasisonflatobjects: Anotherlimitationis thefact thatcomputationalgeometr ydealsprimar ilywith straightorflatobje cts.Toala rgeextent,th isisaconsequenceofCG' ers interestindis cretegeomet- ricc omplexity,asopposedtocontinuous mathem atics.Anotheris suesisthatprovingthe correctnessand efficiencyofanalgorithmi sonly possi blewhenallthecomputationsarewelldefin ed.Many computa tions

onconti nuousobjects(e.g.,s olvingdifferent ialandintegralequations) cannotguaranteethattheirresul ts

arecorrectnor thattheyconverge ins pecifiedamountoft ime.Notethatitispossibletoapproximate curvedobjectswit hpiecewiseplanarpol ygonsorpolyhedra.Thisassumptionhasfreedcomputational geometrytodealwit hthecombinator ialel ementsofmostofthepr oblems,asopposedtodealingwi th numericalissues. Emphasisonlow-di mensional spaces:Onemore limitationisthatcomputationalgeometry hasfocu sedpri- marilyon2-dimensional problems, and3-dimensionalproblemsto alimited extent .Thenicethingabout

2-dimensionalproblemsisthatthey areeasytovis ualizeandeasytounderstand.Butmanyofthedaunting

LectureNotes3CMSC754

applicationsproblemsresidein3- dimensionalandhigherd imensionalspaces.Furthermore ,issuesrelated totop ologyaremuchcleanerin2- and3-d imensionalspac esthanin higherdimensi onalspaces. OverviewoftheSemester: Herearesome ofthetopicsthatwewill discussthissemes ter. ConvexHulls:Convexityisaveryimportantgeomet ricpropert y.A geometricse tisconvexiffor everytwo pointsintheset ,theline segmentjoini ngthemisalso intheset.Oneo fthefirstproble msidentifi edin thefieldo fcomputationa lgeometry isthatofcomputingthesmallestconve xshape,calledtheconvexhull, thatencloses asetofpoints(seeFig.2).

Convexhull

Polygontriangulation

Fig.2:Conve xhull sandpolygontriangulation.

Intersections:Oneofthe mostbas icgeometric problemsisthatofdeter miningwhent wos etsofobjectsin- tersectoneanoth er.Determiningwh ethercomplexobjectsintersectoftenreducestodet erminingwhich

individualpairsofprimitiveentities(e.g., linesegments)inte rsect.Wewilldiscusseffic ientalg orithmsfor

computingtheinters ectionsofas etoflinesegments. TriangulationandPartitioning:Triangulationisacatchwordforthemore genera lpr oblemofsubdividinga complexdomainintoa disjointcol lectionof"simple" objec ts.Th esimplestregionin towhichoneca n decomposeaplanarobj ectis atriangle (atetrahedronin3-d andsimplexinge neral).Wewilldiscuss howtosubdi videapolygon intotrianglesandlater int hesemesterdiscussmore generalsubdivisionsinto trapezoids. Low-dimensionalLinearProgramming:Manyoptimizationproblemsincomputationalgeometrycanbestated inthe formofalin earprog rammingprob lem, namely,findtheextremepoints(e.g. highestorlowest) that satisfiesacollectiono fline arinequalities.Linearprog rammingisani mportantproblem int hecom- binatorialoptimization,andpeopleof tenneedtosolvesuchproblemsinhundredtoperhapsthousand dimensionalspaces.However therearemanyint erestingproblems(e.g.find thesmallestdi scencl osing asetofpoints)thatcanbeposedaslowdimensionallinearprogrammingproblems.In low-dimensional spaces,verysimpleeffic ientsolutionse xist. VoronoiDiagramsandD elaunayTriangulations:GivenasetSofpoint sinspace,oneofthe mostimportant problemsistheneares tneighborproblem. Givenapoint thatisn otinSwhichpointof Sisclo sesttoit? Oneofthe techniquesused fors olvingthispr oblemistosubdividespaceint oregions,accor dingtowhich pointisclos est.Thisgi vesrisetoageometricpar titionof spacecalledaVoronoidiagram(seeFig.3 ). Thisgeometric structurearisesin manyapplicationsofgeometry.Thedualstructure, calledaDelaunay triangulationalsohasmanyint erest ingproperti es. LineArrangementsandDual ity:Perhapsoneofthemostimportantmathematicalstructuresincomputational geometryisthatofan arrangementofli nes(orgeneral lyt hearrangementofcurvesands urfaces ).Givenn linesintheplan e,a narrange mentisjustthegraphforme dbyconsideringtheintersectionpoi ntsasvert ices andli nesegmentsjoini ngthemasedges(seeFig.4). Wewillshowthatsuch astructur ecanbeconstr ucted inO(n 2 )time. Thereas onthatthisstr uctureiss oimportantist hatmanyproblemsinvol vingpointscanbetransformed intoproble msinvolvinglinesbyameth odofpoint-lineduality.Intheplane,thisisatransformationthat

LectureNotes4CMSC754

Fig.3:Voronoi diagr amandDelaunaytriangulat ion.

Fig.4:Anar rangementof lines intheplane.

mapslines topointsand pointstolines (orgener ally,(d!1)-dimensionalhyperplanesindimension dto points,andviceversa). Fore xample,supposet hatyouwanttodeterminewhetheranythreepointsofa planarpointset arecollinear .Thiscouldbe determinedi nO(n 3 )timeb ybrute-forc echeckingofeach triple.However, ifthepointsaredualizedintolin es, then(aswewill seelaterth issemester) thisredu ces tothe question ofwhetherthereisaverte xofdeg reegreaterthanfourinthe arrangement. Search:Geometricsearchpr oblemsareofthefollowinggener alform.Givenadataset(e.g.points,lines,poly- gons)whichwil lnotchange,preproces sthisdataseti ntoa datastruct uresothatsometypeofquerycan beanswer edasefficientlyaspos sibl e.Forexample,considerthefollowingproblem,calledpointlocation . Givenasubdivisionof space( e.g.,aDelaunaytriangulation),determine thefaceofthesubdivisi onthat containsagivenquery point. Anothergeometricsear chproblemisthe nearestneighborproblem:givena setofp oints,dete rminethepointofth esetthatisclosesttoagivenquerypoint.Anotherexampleisrange searching:givenasetofpointsandashape,calledarange,eithercountofreportthesubsetofpointslie withinthe given region.Theregionmaybe arectangle,disc,orpolygonal shape,like atriangle. q pointlocation q p nearestneigh borsearhcing Fig.5:Geometri csear chproblems.Thepoint-locat ionquerydeterminesthetrianglecontainingq.Thenearest- neighborquerydeter minesthepoint pthatisclosestto q. Approximation:Inma nyreal-worldapplica tionsgeometricinputsa resubjectto measurementerror .Insuch casesitmay notbenecessary tocomput eres ults exactly,sincethe inputdatait selfisnot exact.Often the abilitytoproduceanapproximatel ycorrectsol utionleadstomuc hsimplerandfa steralgorithmicsolu tions.

LectureNotes5CMSC754

Considerforexamplet heproblemofcomput ingthediameter( thatis,themax imump airwisedistanc e) amonga setof npointsinspace.In theplaneeffici entsoluti onsareknownf orthisproblem.Inhigher dimensionsitisquitehar dtosolv ethispr oblemexactlyinm uchles sthanthebrute- forcetime ofO(n 2 ).It isea sytoconstructin put instancesinwhichmanypairso fpointsareve ryclosetoth ediametricaldista nce. Supposehowev erthatyouarewillingt osettle foran approximation,say apairofpointsatdis tanceatleas t (1!!)!,where!isthe diametera nd!>0isan approxima tionparametersetbytheuser.Theree xist algorithmswhoserunningtimeis nearlylinear inn,assumingthat!isafi xed constant.As!approaches zero,therunni ngtimeincr eases. Lecture2:Warm-UpProblem: Comp utingSlopeStatistics

SlopeStatis tics:Today,weconsider asimpl ewarm-upexerciseasanexa mpl eofatypicalproblemincomputational

geometry.Tomotivatet heproblem,imagi nethatamedicalexperimentisrun,where thetherapeuti cbenefitsof acertaintreatmentregimenisbeingstudied.Asetofnpointsinreal2-di mensionalspace,R 2 ,isgiven.We denotethiss etbyP={p 1 ,...,p n },wherep i =(a i ,b i ),wherea i indicatestheamountoftreatme ntandb i indicatesthetherapeuticbe nefit.Th ehypothesisisthatincreasingtheamountoftreatment by!aunitsresults ina nincrease intherapeuticbenefito f!b=s(!a),wheresisan unknown scalefactor. Ino rdertostudytheprop erties ofs,astatisticianconsidersthesetofslopesofthelinesjoiningpairs ofa points(sinceeach sloperepresentstheincr easei nbenefitforauni tincr easeint heamountoftreatment).For

1"i s i,j = b j !b i a j !a i ,
(seeFig.6 (a)).Sothatw edon'tnee dtoworrya boutinfinite slopes,letusmaketh esimplifyinga ssumptiontha t

thea-coordinatesofthepointsarepairwised istinct,and toavoidties, letusassu methatthe slopesare distinct.

LetS={s
i,j |1"i8thsmallestslop e

slope slope minimum slope minimum slope minimum slope (a)(b)

Fig.6:Thesl opes

i,j andthe slopesetS={s i,j |1"iMin/Max:Computethemini mumormaximumsl opeofS. k-thSma llest:Computethek-smallestelementof S,givenanyk,1"k" ! n 2 " .

Average:Computetheav erageofthe elementsofS.

Rangecounting: Givenapairofrealss

! "s + ,returnacountofthenumberofelementsofSthatlieinthe interval[s ! ,s + ].

LectureNotes6CMSC754

CountingNegative SlopesandInversions:Inthis lecturew ewillconsiderthela stproblem ,thatis,c ountingthe

numberofslopesthatliewithinagiveninterval[s ! ,s + ].Beforeconsideringthegeneralproblem,letusconsider asimplerversionbyconsideringthecasewheres ! =0ands + =+#.Inotherwords,wewillcountthe numberofpai rs (i,j)wheres i,j isno nnegative.Thisproblemisinterestingstatistically,becauseitrepresents thenumbe rofinstancesinwhichinc reasingth eamountoftreatmentresult sinanincreaseinthetherapeut ic benefit. Ourapproach willbetocountthenumber ofpairs suchthat s i,j isstrictly negativ e.Thereisnolossofgenerality indo ingthis,sincewecan simplysubtrac tthecountfro m ! n 2 " too btainthenumberof nonneg ativeslopes.(The reasonforthisothe rformulatio nisthatit willallowustointroducetheconceptofin versioncount ing,whi ch willbeus efulf orthegeneralproblem.)Itwill simplifythepresentationtomaketheassumptiont hattheset sof a-coordinatesandb-coordinatesaredistinct. Supposewebegin bysor tingthepointsof Pininc reasingorderbytheira-coordinates.LetP=$p 1 ,...,p n %be theresulting orderedsequence ,andletB=$b 1 ,...,b n %bethe associated sequenceofb-coordinates.Observe that,for1"ib j ifan donlyifs i,j isne gative.For1"ib j .Clearly,ourtaskreducestocountingthenumberofinversionsofB(seeFig.7 (a)). (a)(b) a 1 a 2 a 3 a 4 b 2 b 4 b 1 b 3

3inv ersions

3negative slopes

51042986

012456

3in versions

6induces

B L :B R : M: Fig.7:Inv ersi oncountingandapplicationtocountingnegativeslopes. InversionCounting:Countingthenumberofin versionsi nas equenceofnnumbersisas impleexer cise, whichcan besol vedinO(nlogn)time.Normally, suchexerciseswillbe leftforyouto do,butsincethisisthefi rsttime topre sentanalgorithm,let'sdo itinfullde tail. Thealgor ithmisasimplegeneralizat ionoftheMer geSortal gorithm.RecallthatMergeSort isaclass ical exampleofdivide-an d-conq uer.Thesequenceispartitionedintoaleftandrightsubsequence,denotedB L and B R ,eachofsizeroughlyn/2.Thesetwosubsequencesaresortedrecursively,andthentheresultingsorted sequencesarethenmergedtoformth efinalso rtedsequence .

Toge neralizethistoinversioncounti ng,inadditio ntore turningthesorted subsequences,the recursivecalls

returnthecou ntsI L andI R ofthe inversi onswithineachoft hesubs equences.Inthe mergingprocesswecount theinversio nsIthatoccur betweenthetwosub sequenc es.Thatis,foreachelementofB L ,wecomputethe numberofs maller elementsinB R ,andaddthesetoI.Intheend,wereturnthetotalnumberofinversions, I L +I R +I. Thealgor ithmispresentedinthecodebl ockbelow.T omergethesubs equences,wemaintaintwoindi cesiand j,whichindicatethecurrentelementsoftherespectivesubsequencesB L andB R .Werepeatedly 2 copythe smallerofB L [i]andB R [j]tothe merged sequenceM.Becausebothsubsequencesaresorted,whenwecopy B L [i]toM,B L [i]isinv ertedwithrespecttotheeleme ntsB R [1...j!1],whosevaluesaresmallerthanit(see Fig.7(b)). Therefore,weaddj!1toth ecount Iofin versions. Themain loopstopsei therwheniorjexceedsthenumberofele mentsini tssubsequence.Whenw eexit,on e ofthe twosubsequences isexhausted.Weappend theremainingelementsoftheothersubsequencetoM.In 2

Moreformally ,wemaintaintheinvariantt hatB

L [i]>B R [j ! ]for1!j ! !j"1andB R [j]#B L [i ! ]for1!i ! !i"1.

LectureNotes7CMSC754

particular,ifi"|B L |,weappendtheremaining|B L | !i+1elementsofB L toM.Sincetheseelementsare alllargert hananyelementofB R ,weadd(|B L | !i+1)|B R |tothei nversionc ounter.(Whencopyingthe remainingelementsfromB R ,thereisnoneedtomodifytheinversioncounter.)Seethecodeblock belowfor thecomple tecode.

InversionCounting

InvCount(B)[Input:asequenceB;Output:sortedsequenceMandinversio ncountI.] (1)PartitionBintodisjo intsubsetsBLandBR,ea chofsizeatmos t!n/2",wheren=|B|; (2)(BL,IL)#InvCount(BL); (BR,IR)#InvCount(BR); (3)Le ti#j#1;I#0;M#$; (4)While(i%|BL|andj%|BR|) (a)if(BL[i]%BR[j])appendBL[i++]toMandI#I+(j&1); (b)elseapp endBR[j++]toM;

Onexittin gtheloop,eitheri>|BL|orj>|BR|.

(5)Ifi%|BL|,appendBL[i...]toMandI#I+(|BL|&i+1)|BR|; (6)Else(we havej%|BR|),a ppendBR[j...]toM; (7)return (M,IL+IR+I); Therunni ngtimeexactly matchesthatofMergeSort. Itobeysthewellkn ownrecurre nceT(n)=2T(n/2)+n, whichs olvestoO(nlogn). Bycombini ngthiswitht heabovereductionf romsloperangecountingovernegat iveslopes,weobt ainan O(nlogn)timea lgorithmforcountingnon negativ eslopes. GeneralSlopeRange Counting andDuality: Now,letusconsiderthe generalr angecountingpr oblem.Let[s ! ,s + ] bethe rangeofslopes tobecounted.I tis possibletoadapt theaboveinversion-countingapproach,subjectto anappropr iatenotionof"order".Inordert omotivatethi sapproach,wewill applya geometrictransfor mation thatconverts theproblemintoaformwherethis orderismo reapparent.Thistransf ormation,call edpoint-line dualitywillfindman yuses laterinthesemester .

Tom otivateduality,observeth atapointinR

2 isde finedbytwocoordinates,say (a,b).Anonverticalline lineinR 2 canals obedefinedbytwoparamet ers, asl opeandy-intercept.Inparticular,weasso ciate apoint p=(a,b)withtheline y=ax!b,whoseslopeisaandwhos ey-interceptis!b.Thislineiscalledp'sdual andis denotedbyp " .(Thereasonforthenegatingtheinterceptwillbecomeapparentshortly.)Sim ilarly,given anynonver ticallineinR 2 ,say":y=ax!b,wedefineitsdualtobe thepoint " " =(a,b).Notethatthedual isain volu tory(self-inverse)mapping,inthe sensethat(p " ) " =pand(" " ) " =". Laterint hesemesterwe willdiscus sthevariousproperties ofthe dualtransfor mation. Fornow,weneedonlya property.Considertwopointsp i =(a i ,b i )andp j =(a j ,b j ).Thecorrespondingduallinesarep " i :y=a i x!b i andp " j :y=a j x!b j ,respectively.Assumingthata i &=a j (thatis,thelines aren otparalle l),wecanco mpute

thex-coordinateoftheirintersectionpoin tbyeq uatingtheright-handsidesofthes etwoequations,whi chyi elds

a i x!b i =a j x!b j 'x= b j !b i a j !a i .

Interestingly,thisisjusts

i,j .Inotherwords,wehavethefollowingnicerelationship:Giventwopoints ,the

x-coordinateoftheintersectionofthe irduallin esisthesl opeoft heli nepassingt hroughthepoints(seeFig.8 ).

(Thereasonfor negatingthebcoordinateisnowevident. Otherwise,we wouldgett henegationofthe slope.)

SlopeRangeCounting int heDual:Basedontheabo ve observations ,weseethatthepr oblemofcountingtheslopes

ofSthatliewithinthein terv al[s ! ,s + ]canber einter pretedinthefollowingequivalentform. Givenasetofn nonverticallinesinR 2 andgiv enaninterval[s ! ,s + ],countthepairsoflineswhoseintersectionsliewithinthe verticalslabwhoselefts ideisx=s ! andwhose rightsi deiss + (seeFig. 9(a)).

LectureNotes8CMSC754

(a)(b) a i a j b i b j s i,j = b j !b i a j !a i s i,j = b j !b i a j !a i p " j :y=a j x!b j p " i :y=a i x!b i p j p i x y

Fig.8:Point- line dualityandtherelationshipbetweent heslopeofalineb etweentw opo intsand thex-coordinateof

theduals ofthetwopoints. (a)(b) x y s ! s + 6 5 4 3 2 1 6 4 2 1 3 5

4intersections

6 4 2 1 3 5

4inv ersions

Fig.9:Inter secti onsintheverticalslab[s

! ,s + ]andin versioncounting.

LectureNotes9CMSC754

Howcanwecountthe numberofs uchinters ectionpointsef ficiently?Again,this canbedonethroughinv ersion

counting.Toseet his,observ ethattwo linesintersectwithinthe slabifand onlyifthe orde roftheirinte rsection

withthelef tside oftheslabisthe inverseof theirinters ectionwiththe right sideofthe slab. Weca nreduceth eproblemtoinversi oncountin g,therefore,asfol lows.First,considertheorderin whichthe linesintersect theleftsideoftheslab(take nfromtopto bottom).Inpartic ular ,theliney=a i x!b i intersectsat thepoint y=a i s ! !b i .Sortthelinesaccordingindecreasingorderofthesey-coordinates,thusobtainingthe orderfromt optobottom,andrenumber themfrom1 tonaccordingtothisor der(seeFig. 9(a)).Next,comput e

theorder inwhichthe(renumbere d)lin esintersectth erightsideoftheslab.Inparticular,lineiisasso ciated

withthev aluey=a i s + !b i .LettingY=$y 1 ,...,y n %denotetheres ultings equence,itiseasytoseethat thenumbe rofinversionsin!Yiseq ualtothenumberofpa irsof linesthat intersectwithintheslab.T hetime toco mputetheintersectionalong theleftside andsortaccordingtothisorde risO(nlogn),andthetimeto computetheint ersectionswi ththerightsideandcounttheinversionsisalsoO(nlogn).Therefore,thetotal runningtimeisO(nlogn). NegativeSlopeRangeCountingRevisit ed:Bythe way,youmight wonderwhattheearlier ins tanceofcounting negativeslopesmapstointhisi nstance.Inthis caset heintervalis[!#,0].Observethataverticallineat x=!#(fromtoptob ottom)in tersec tsthelinesinincreasingord erofslope,orequivalently,inorderofa- coordinates.Thus,sortingthe pointsfrom toptobottomorderbyt heiri ntersectionwith s ! =!#iseq uivalent tothe sortingbya-coordinates,whichisjustwhatwewe didinthecaseofne ga tiveslop es.

Theri ghtsideofthesl abisdeterminedbyt het op-to-bottom orderofinter secti onsofthelineswithverticalline

atx=0.Clearly,lineiintersectsthisverticalaty=!b i .Therefore,countingtheinversionsofthesequence !Y=$!y 1 ,...,!y n %iseq uivalenttotheprocessofcountinginversio ns inthesequenceB=$b 1 ,...,b n %, exactlyaswedidbefor e.Thu s,thec aseofcoun tingnegativeslopescanindeed beseentobea specialcaseof thisalgorith m. Review:Insum mary,wehaveseenhowan appare ntly2-dimensionalg eometricprobleminv olvingO(n 2 )(implicitly defined)object scanbesolvedin O(nlogn)timeth roughreductiontosimple1-d imensionalsortingalgorithms. Namely,weshowed howto solvethesloperangecounting problemin O(nlogn)time.Thep roblemsof computingtheminimumand maximumslopescan alsobesolved inO(nlogn)time.Wewillle avethisp roble m asane xerci se.Theproblemofcomputingthek-thsma llestslopeisaconsid erablyharder prob lem. Itisnot toohardto devisearando mized algorithmwhoserunn ingtime isO(nlog 2 n).Suchanalgorithmappliesa sortof"ra ndomize dbinarysearch"indualspacetolocatetheintersectionpointofthedesiredrank.Improving theexpe ctedrunningtimetoO(nlogn)timeis ano ntriv ialexercise,andmakingthealgo rithmdeterministicis evenmorec hallenging.I donotknowofanefficientsolutiontotheproblemofcomputingtheaverageslope. Thereduct ionofageometricproblem to1- dimensi onalsortingands earching isquitecommonincomputational geometry.Wewillseeot herexamplesoft hislaterint hesemester.Wehave alsoseena niceapplicationo fthe notionofpoint-li neduali ty,whichwillbeseenmanymoreti mesthiss emester.

Lecture3:ConvexHulls

Convexity:Letuscons idera fundamentalstructure incomput ationalgeometry,calledtheconvexhull.Wewillgive

amoreformaldefinitionlater,but,givenasetPofpoi ntsintheplane,t heconvexhul lofP,denotedconv(P), canbedefined intui tiv elybysurroundingacollectionofpointswitha rubberbandandthenlett ingt herubber band"snap" tightlyar oundthepoints(seeFig.10). Thereareanumber ofreasonst hatthe conve xhull ofapointsetisanimportantgeometricstructure.Oneis thatitisoneo fthe simplest shapeappro ximationsfo rasetofpoints.(Otherexamplesincludeminimumarea enclosingrectangles,circl es,andellipses.)Itcanal sobeusedforapproximatingmorecomplexshapes.For example,theconvexhullofa polygoni ntheplaneorp olyhedronin 3-spaceist heconvexhullofi tsvert ices. Alsomanyalgorithms computetheconvex hullasaninitialst agein theirexecut ionortofilterout irrelevant points.Forexample,thediameterofapoi ntset isthemaximum distancebetween anytwo pointsoftheset.It

LectureNotes10CMSC754

Pconv(P)

Fig.10:Apoint setand its convexhull .

canbes hownt hatthepairofpoints determining thediameterarebothver ticesofthe convexhull.Alsoobserve thatminimumenc losingconvex shapes(suchastheminimumar earect angle,circle,andellipse) dependonly onthe pointsofthe convexhull. Convexity:AsetKisconvexifgi venanypointsp,q(K,thelinesegmentpqisen tirelycontainedwithinK. Boundedness:Aconvexbodymaybebounded,meaningthatitcanbeenclosedwithinasphe reof afixed radiusorunboun ded,me aningthatitextendstoinfinity.Examplesofunbounded conve xsets intheplane includelines,rays,halfpla nes,theregion lyingtoonesid eofaline,andinfinitecones.Givenaline",the setofpo intslyinge ntirelytoonesideof"(possiblyincluding"itself)iscalle dahalfplane. Support:Animportant propertyofany convexsetKinthe planeis thatateverypoin tponthe boundaryof K,thereexistsaline"(orgene rallyinhyperplaneinhigher dime nsions)thatpassesthr oughpsuchthat Kliesentirely inoneoftheclosed halfp lanesdefin edby". Convexhull:Theconvexhullofany setPisthe intersection ofallconvexsetsthatco ntainsP,ormore intuitively,thesmallestconvexsetth atcon tainsP.Wewilldenotethisconv(P). Whencomput ingconvexhulls,wewillusual lytakePtobe afinitese tof points.Insucha case,co nv(P)willbe aconvexpolygon.GenerallyPcouldbeaninfini tes etofpoi nts.Forexample,wecould talkaboutthe convex hullofacoll ection ofcir cles.Theboundaryofsuchashapewouldconsist ofacombinationofcircularar csand straightlinesegments. ConvexHullProblem:The(pl anar)convexhullproblem is,gi venasetofnpointsPinthe plane,o utputarep- resentationofP'sco nvexhull.Theconvex hullisaclosedc onvexpoly gon,thesimplestrepresentationisa counterclockwiseenumerationofthevertices oftheconvexhull.(Althoughpoint sofPmightliein theinterior ofanedge ofthe boundaryof thecon vexhull, suchapoint isno tconsideredavertex.Sincewewillassumethat thepoints areingeneralposition,andinparticular,nothreearecollinear,thisissuedoesnotari se.)Although theoutpu tconsistsonlyofthebou ndaryofthehull, theconvexh ullofPisac onv expolygon,whichmeanstha t itinc ludesboththeboundaryan dinteriorofth ispolygo n. Graham'sscan:Wewi llpresentanO(nlogn)algorithmforconvexhulls .Itisa simplevariationof afamous algorithmforconvexhulls, calledGraham'sscan.Thisalgorithmdatesbacktotheearly70's.Thealgorithmis looselybasedona commonapproachfo rbuilding geo metricstructurescalledincrementalconstruction.Insuch aalgorithmobject(pointshere)areaddedoneatatime,andthest ructure(convexhullhere)isupdated with eachnew insertion. Animportant issuewithincremental algorithmsistheorderofins ertion.Ifweweretoaddpointsins ome arbitraryorder,wewouldneedsomemet hodoftestingwhethe rthenewlyaddedpointisinsidetheexisting hull.Itwills implifyt hingstoaddpoints insomeappropriatelysortedo rder,inourc ase,inincreasingorder ofx-coordinate.Thisguaranteesthatea chnewlyad dedpointisoutsidethecurrenthull .(Notethat Graham's originalalgorithmsort edpointsinadifferentway .Itfoundthelowestpointinthedatasetandthensortedpoints cyclicallyaroundthispoint.S ortingbyx-coordinateseemstobeabiteasie rtoimplement,how ev er.) Sincewearew orking fromleft toright,itwould beconvenientiftheconvexhullverticeswerealsoorderedfrom lefttoright. Asmen tionedabove ,the convexhullisaconvex polygon,whichcan berepresented asac yclic sequenceofvertices.Itwillmake mattersab itsimplerforustorepresentthisconvexpolygonastwochains,

LectureNotes11CMSC754

onerepr esentingitsupperpart,calledtheupperhull andoner epresent ingthelowerpart,calledthelowerhull (seeFig. 11(a)). p n p 1 upperhull lowerhull (b)(a)

H[top]

H[top!1]

H[top!2]

Fig.11:Upperand lower hulls .

Thebreakpointscommonto bothhulls willbethe leftmostandright mostverticesoft heconv exhull,t hatis,the

pointsofPhavingthesmalles tandlargest x-coordinates,respectively.(Bygene ralposition,wemayassume therearenodu plicatex-coordinates,andsotherewillbeauniqu eleftmostpoin tan duniquerightmostpoints.) Afterbuildingboth,the twohullscanbeconcatenated intoasinglecyclicco unterclockwiselist.

Letusj ustcons iderhowtocomputet heupperhull,since thelowerhullis similar.Reca lltha tthepointsofPare

firstsortedin increasingorderoftheirx-coordinates,andtheywillbeaddedo ne-by-one. Westorethevertices ofthe currentupperhull inastackH,wherethetopofthestackcorrespondstothemostrecentlyaddedpoi nt ofP.LetH[top]denotethetop ofthestack, andletandH[top!1]denotetheelement immediatelybel owthe

top.Observeth ataswereadthestac kelementsfromto ptobot tom(thatis, fromrighttoleft)c onse cutive triples

ofpoint softheupperhullwil lmake a(stri ct)"l eft-handt urn"(seeFig .11(b)).A swepushnew pointsonthe stack,wewillmainta inthisprop erty,byp oppingpointsoffofthe stackift heyfailtosat isfyt hisproperty. Turningandorientati ons:Beforeproceedingwith thepresentationof thealgorithm,w eshouldfirstmakeashort digressiontodiscussthemeaningof"l eft-handtur n."Givenanorderedtripleofpoints$p,q,r%inthe plane,

wesay thattheyhave positiveorientationifthe ydefineaco unterclockwiseorientedtria ngle (seeFig.12(a)),

negativeorientationifthe ydefineaclo ckwiseorientedtriangle(see Fig. 12(b)),andzeroorientation ifthe yare

collinear,whichincludesaswellt hecasewheret woormoreofthepointsareidentical(seeFig.12(c)).Note thatorientation dependsontheorderinwh ichthepointsaregiven. (a)(b) (c) p q r p q r p q r p=r q orient(p,q,r)>0orien t(p,q,r)<0orien t(p,q,r)=0

Fig.12:Orient ations oftheorderedtriple(p,q,r).

Orientationisformally definedasthe signofthedeterminantofthepointsgiveninhomogeneouscoordinates, thatis,byprep end inga1toe achcoordinate.Forexample,intheplane ,wedefine

Orient(p,q,r)=det

# $ 1p x p y 1q x q y 1r x r y % & .

LectureNotes12CMSC754

Observethatinthe1-dimensionalcase, Orient(p,q)isjust q!p.Henceitispositiveifpq.Thusorientationgeneralizes<,=,>in1-d imensionalspace.Alsonotethatthesignof the

orientationofanorderedtriplei sunchangedi fthe pointsaretran slated,rotated,orscaled(bya positivescale

factor).Areflectiontran sfo rmation,e.g.,f(x,y)=(!x,y),reversesthesignoftheorientation.Ingeneral, applyinganyaffinetr ansformation tothepoi ntaltersthesignoft heori entationaccordi ngtothesignofthe matrixusedin thetransformation. Givenasequenceofthree pointsp,q,r,wesaythatthesequence$p,q,r%makesa(str ict)left-handturnif

Orient(p,q,r)>0.

Graham'salgorithmcont inued:Letp

i denotethenext pointtobeadded inthelef t-to-r ightorderingoft hepoint s (seeFig.1 3(a)).Ifthetriple$p i ,H[top],H[top!1]%formsastrictleft-ha ndtu rn,thenw ecansimplypushp i ontothest ack.Otherwise, wecaninferthatthe middlepointofthe tripleH[top]cannotbe onthe upperhull ,

andso wepopitoff thes tack.W erepeatthis untilreachi ngapositivelyorientedtriple(seeFig. 13(b)),orthere

arefewert hantwoelementsont hestack.Thepoppi ngprocessendswhenp i 'spr edecessoronthestackisits predecessorontheconvexhul l(s eeFig.13(c)) .Thealgorithmis presentedin thecodeblockbelow. (b) p i p j (c) pop p i p j (a) processingp i afteraddingp i p i p j pop beforeaddingp i

Fig.13:Graham's scan.

Graham'sScan

(1)Sortthe pointsaccordin gtoincre asingorderofth eirx-coordinates,denoted'p1,p2,...,pn(. (2)pushp1andthenp2ontoH. (3)for i#3,...,ndo: (a)while(|H|)2andOrient(pi,H[top],H[top&1])%0)popH. (b)pushpiontoH. Correctness:WhyisGr aham's algorithmcorrect?Wecans howinductivelythatthe contentsofHatany stageof thealgorith mconstitutetheupperhu llofthepointsthatha vebe enprocessed sofar.Fortheinductionbasis (H={p 1 ,p 2 })thisistriviallytrue.Fortheinductionstep,observethatp i isth erightmostp ointamongthe pointsprocesseds ofar,andthereforeit mustlieon theupperhull.Letp j bethe neighboringv ertextop i on theuppe rhullofthefirstipoints(seeFig.13( a)).Itiseasy toseet hatp j mustbeinHpriortotheaddit ion ofp i .Eachpointp k inHthatliesbetwee np j andp i liesben eaththeedgep j p i ,andsop k shouldnotbepart ofthe upperhullafter p i isad ded.Foreachsuchpoint itiseasytoseeth atOrient(p i ,p k ,p j )"0.Itfollows that,aseach ofthesep ointsp k isteste dwithinthewhileloo p,itwillbe deleted .(Weareb eingabitslo ppy here,becausethi sisnotexact lythesameorient ationtes tmadebyt healgor ithm,since p j isno tnecessarilyp k 's predecessoronthestack.W e'll leavefixing thisproofupasa nexercise.)

Finally,whenp

j reachesthetopofthestacke itherfind thatp j =p 1 ,andhencetherearelessthantwoelements

onthe stack,orwefind thatwefinallyhave the tri plet hatsatisfiestheorienta tiontest.Ine ithercase,theloop

terminatesandp i ispu shedonthestack,asde sired. Thelo werhullcanbecomputedbyan essentiall ys ymmetri calgorithm,butworkingfr omrightto leftinstead. Oncethetw ohulls arecomputed,wesimply concatenatethetw ohullsintoasinglecircularlist.

LectureNotes13CMSC754

Running-timeanalysis:Wewi llshowthatGr aham'salgori thmrunsinO(nlogn)time.Clea rly,ittakesthismuch timefor theinitialso rting.Afterth is,wewillshowtha tO(n)timesu fficesfortherestofthecomp utation. Letd i denotethenumberof pointsthatar epopped( deleted) onprocessingp i .Becauseeachorientationtest takesO(1)time,theamo untoftime spentprocessingp i isO(d i +1).(Theextra+1isfor thelastpo inttested, whichisnot deleted.)Thus ,thetotal runningtime isproportionalto n ' i=1 (d i +1)=n+ n ' i=1 d i .

Tobo und

( i d i ,observethateachofthenpointsispushedont othestack once.Onceapointi sdeleteditcan neverbedeletedagai n.Since eachofnpointscanbedeletedat mostonce, ( i d i "n.Thusaftersorting,the totalrunningtime isO(n).Sincethisistrueforthelowerhullaswell,thetotaltimeisO(2n)=O(n). ConvexHullbyDivide-and-Conquer: Aswiths orting,ther earemanydifferent approachestosolv ingtheco nvex hullproblemf oraplanarpointset P.NextwewillconsideranotherO(nlogn)algorithm,whichisbasedon thedivid e-and-conquerdesigntechnique.ItcanbeviewedasageneralizationofthefamousMergeSortsorting

algorithm(seeanystandardal gorithmstext). Hereisan outlineofthe algorithm.It beginsb ysortingthepoints

bythei rx-coordinate,inO(nlogn)time.There mainderofthe algorithmisshowninthecodese ctionbelow .

Divide-and-ConquerConvexHull

(1)If|P|%3,the ncomputethe convexhullbybrutefo rceinO(1)timeand return.

(2)Otherwis e,partitionthepointsetPintotwose tsAandB,whereAconsistsofhalfthepointsw iththelow estx-coordinates

andBconsistsofhalfofthepo intswiththe highestx-coordinates. (3)Recurs ivelycomputeHA=conv(A)andHB=conv(B). (4)Merge thetwohullsintoacommo nconve xhull,H,by computin gtheupperandlowertangen tsforHAandHBand discardingallthepointslyingbetwee nthese twotange nts. Theasympt oticrunningtimeofthealgori thmcanbeexpress edbyarecurrence.Givenaninputofsizen,

considerthetimeneeded toperform allthepartsoft hepr ocedure,ignoring therecursivecalls. Thisincludes the

timetop artition thepointset,compu tethetwota ngents,andreturnthefinalresult.Clearlythefirstandthirdof

thesestepscan beperformedinO(n)time,assumin galinkedlistrepresen tation ofthehullvertices.Belowwe wills howthatthetangentscanbecomputedin O(n)time.Thu s,ignoringconstant factors,wecandescribeth e runningtimebythefollowin grecurren ce. T(n)= )

1ifn"3

n+2T(n/2)otherwise. Thisisthe samerecurrence thatarises inMergesor t.Itiseasytosh owth atitsolvestoT(n)(O(nlogn)(see anystandard algorithmstext).All thatremainsisshowinghowto comput ethetwotangents. Onething thatsimplifies theproces sofcomputingthetangentsisth atth etwopointsets AandBareseparated

fromeac hotherbyavertica lline(assumingnodu plicatex-coordinates).Let'sconcentrateonthe lowertangent,

sincetheuppe rtangen tissymmetric.Thealgo rithmoperatesbyasimple"walking"procedure.Weinitialize atobe therightmost pointof H A andbisthe leftmostpoin tofH B (seeFig.1 4(a)).Thesetwo pointscanbe computedinli neartime. Lowertangencyi saconditionthatcan betested locall ybyanorientationtestinvolvingthet woverticesand neighboringverticesonthe hull.Weiteratethefol lowi ngtwolo ops,whichmarchaandbdown,until they reachthepointslo wertang ency(seeFig.14(a )-(c)).Givenapointaonthe hull,leta.succanda.preddenote itssuc cessorandpredecessorinCC Worderabo utthehull.

Thecondition"abisnotthelowertangentofH

A "canbeimplementedwiththeorientationtestOrient(b,a,a.pred))

0,andtheothertestforH

B isan alogous.Provingthecorrectnessofthis procedureisalittletrick y,butnottoo

LectureNotes14CMSC754

AaABB B

a b b b (a)(b)(c) lowertangent uppertangent A a

Fig.14:Computing thel owertangent.

FindingtheLowerTan gent

LowerTangent(HA,HB):

(1)Let abetherig htmostp ointofHA. (2)Let bbethelef tmostpo intofHB. (3)While(abisno talowertang ent forHAandHB)do (a)While(abisno talowertang ent toHA)doa#a.pred(mov eaclockwise). (b)While(abisno talowertang ent toHB)dob#b.succ(movebcounterclockwise). (4)Returnab. hard.(Theis sueispro vingthatthetwoinner whileloopsne vergobe yondthe lowertangentpoi nts.)See O'Rourke'sbookoutforacarefulproof .Theimpor tantthing istha teachverte xoneachhullca nbevisitedat mostoncebythes earch, andhenceits runningtime isO(m),wherem=|H A |+|H B | " |A|+|B|.Thisis exactlywhatweneede dtogettheovera llO(nlogn)runningtime. Gift-WrappingandJarvis'sMarch:Thenext algorithmt hatwewillconsiderisavari antonanO(n 2 )sortingalgo-

rithmcalle dSelectionSort.Fo rsorting,thisalgorithmrepeatedlyfindsthenext elementt oaddtothe sortedorder

fromtherem ainingitem s.Thecorrespondingconv exhullalgorithmiscalledJarvis'smarch.whichbuildsthe hullinO(nh)timeby aprocess calle d"gift-wrapping".Thealg orithmoperatesbyconsid eringany onepoint thatisontheh ull,sa y,thelowe stpoint. Wethenfindth e"next"ed geonthehullinco untercloc kwiseorder .

Assumingthatp

k andp k!1 werethelasttw opointsadded tothehull,computethepoint qthatmaximizesth e angle!p k!1 p k q(seeFig. 15).Clearly,w ecanfindthe pointqinO(n)time. p 0 =(!",0) p 1 p 2 p 3 q

Fig.15:Jar vis' smarch.

Afterrepeatingthishtimes,wewillretu rnb ack tothestartingpoin tandwearedone.Thus ,theover allrunning timeisO(nh).Notethatifhiso(logn)(asymptoticallysmallerthanlogn)thenthisisabettermethodthan

Graham'salgorithm.

LectureNotes15CMSC754

Onetechnicaldetail isthatwhen wetofind anedgef rom whichtostart.Oneeasywaytodothisistoletp 1 be thepoint withthelowesty-coordinate,andletp 0 bethe point(!#,0),whichisinfinitelyfartotheright.The pointp 0 ison lyusedforcomp utingtheinitiala ngles,afte rwhichitisdisc arded(seeFig.15).

Lecture4:MoreonConvexHull s

OutputSensitiv eConvexHullAlgorithms:Weha veseentwoalg orithmsforp lanarconv exhull,Graham'salgo- rithmand thedivide-an d-conqu eralgorithm,thatbothruninO(nlogn)time.Weha vealsose enJarvis's algorithm,whichrunsinO(hn)time,wherehisthe numbero fverticesonthehull.

Traditionally,algorithmsareanalyzedinte rmsoftheirrunningtimeas afunctionofinputs izeal one.Ho wever,

manygeometricalgorithms produceoutputswhoses izesvarygreatly(fromaconstant uptoalargepolynomial inn).Fo rsuchproblem s,itiscommon toexpressrunningtimeasafunctionofboththeinp utandth eoutput sizes.Suchan algorithmissaidtobeoutputsensit ive.Jarvis'salgorithmissuchanexample. Whenhisasy mptoticallysmallerthanlogn,Jarvis'salgorithmissuperiortoGraham'salgorithm.Sinceneit her algorithmisoptimalinall cases,iti snaturaltowonderwhe therthereissome "ultimate"plana rco nvexh ull algorithmthatisoptimalwit hrespectto bothnandh.

Sincetheobject iveist ooutputthepointsonthehulli ncyclicord er,itisprettyeasytoseeth atth isre quiressort-

ingthepo intsofthe hull.Itiswellknownth atany comparison-basedalgorithm forsortingrequires"(nlogn) time. 3 Ifwe ignorehandconsi dertheworstcase inwhichall ofthepointsarevert icesoftheco nvexhu ll,then itisp rettye asytoprovetha tthe"(nlogn)lowerboundc annotbebeaten.(We leavetheproofofthisasa n easyexerci se.Laterinthesenoteswepresentanout putsensitivelowerbou nd.) Today,wepresenta planar convexhullalgorithm, cal ledChan'salgorit hm,whoserunningtimeisO(nlogh), andweshow thatth isisessenti allythebestp ossible.Whil ethisalgorit hmistoosmallanimprovemento ver

Graham'salgorithmtobepractical, itisquiteinteresting nonethelessfromtheperspect iveofthetechniques that

ituse s. •Itisd eriv edbasedonacombinationo ftwosloweralgorith ms,Graham'sandJarvis's. •Itisb ased on"knowing"the finaln umberofverticesontheconvexhu ll.Sincethisnum berisnotknown, itad optsaninterestingguessin gprocess todetermineitsvalue(roughl y).Itisremarkablethatthet imeto runthegu essingversio nisasymptoticallythesam easifyouhadknown thenumberinadv ance! HowtoBeatGraham andJarvis:Tomo tivateChan'salgorithm,o bservethattheprobl emwithGraham'sscanis thatitsortsall thep oints,and henceis doomed tohavingan"(nlogn)runningtime,irrespective ofthesize

ofthe hull.Onthe otherhand,Jarvis's algor ithmisnot limitedinthisw ay. Unfortunate ly,itiswaytooslow if

therearemanyp ointsonth ehull.So,how canwecombinethe setwoinsights toproduceafaster solutio n? Thefirs tobservationneededf orabetterapproachisthat,ifwehopeto achieve arunning timeofO(nlogh), wecanonly aff orda logfactordependingonh.So,ifwerunGraham'salgorithm,wearelimitedtosorting setsofsize atmosth.(Actually,anypolynomialinhwillwor kaswell.Thereasonis that,for anycons tantc, log(h c )=clogh=O(logh).Forexample,loghandlog(h 2 )areasymptot icallyequivalent.Thisobservation willcomein handylateron.) Howcanweuse thisobser vation?Suppos ethatwepartitionedthesetinto roughlyn/hsubsets,eachofsize h. Weco uldcomputetheco nvexhullofeachsubset intimeO(hlogh),whichwe'llcallaconvexmini-hull.The totaltimetocompu teall themin i-hullswouldbeO((n/h)hlogh)=O(nlogh).Wearewithinouroverall timebu dget,butofcoursewewould stillhavetofigu reouth owtomer gethesemini-hullsinto thefinalglob al convexhull. 3

Recallthatasymptoti c!-notationisthe lower -boundanalogto theO-notationupperbound.Formall y,wesaythatafun ctionf(n)is!(g(n))

if,asntendstoinfinity ,theratio g(n)/f(n)isbounded. Thatis,fgrowsatleastasfas tasg.Th erearefastersor tingalgo rithmsthatarenot

comparisonbased,buttheyappl ytodiscreteobject ssuchassmallintege rsandstrings,nottorealn umbers.

LectureNotes16CMSC754

Butwai t!Wedonotknowtheval ueofhinad vance,soitwouldseemthatwearestuck befo rewe evenget started.Wewilldea lwiththisc onundru mlater,but,justtogetthe ballrolli ng,supposefor nowthatwehadan estimateforh,callith " ,whosevalueisatleastaslargeash,butnottoomuchlarger(sayh"h " "h 2 ).Ifw e runtheab ovepa rtitioningprocessusingh " ratherthanh,thetotalrunningtimetocomputeallthemini-hullsis

O(nlogh

" )=O(nlogh).

Originalpoin tset

(a)(b)

Partition(h

! =8) andmini-hulls

Fig.16:Part iti onandmini-hulls.

Thepart itioningofthepointsisdonebyanyarbit rary method(e.g.,justbreaktheinputupintogroupsofsize roughlyh " ).Of course,th eresultingmini-hullsmighto verlapo neanother(seeFig.1 6(a)and (b)).Although wepres umethath " isaro ugh approximationtoh,wecannotinferanythingaboutthenumbersofverticeson thevariou smini-hulls.Theycouldran gefrom3upto h " . Mergingtheminis:Thequest ionthatremainsishowt omergethe mini-hullsinto asingleglobalhull.Theideaisto runJarvis's algorithm,butwetre ateachmini-hullasifitisa"fatpoint".Ateachstep,ratherthancomputing

theangle fromthecurrenthull vertextoe verypo intoftheset,wec ompu tethetangentlinesof thecurren thull

vertextoeacho fthemi ni-hulls,inc ludin gthemini- hullcontainingthisvertex. (Therearetwot angentsfroma

pointtoami ni-hull,and weneedt otakecaretocomputetheproperone.) Notethatthe currentvert exison the globalconvex hull,soitcannotlie intheinterior ofanyofthemini -hulls.Amongallthesetangents,wetake

theoneth atyieldsthe smallestexternal angle.(Theproce ssisillustratedinFig.17(a).)Notethat,eventhough

apointcanappearonlyonceonthefinalglobalhull,asinglemini-hullmaycontribute manypoin tstothefinal hull. Youmigh tthinkthat,sin ceamini-hullmay haveasmanyash " vertices,thereisnothingto besavedincom- putingthesetangents overthestrai ghtforwardmethod. Thekeyisth ateach mini-hullisa convexpolyg on,and

henceit hasquiteabi tmore structurethan anarbi trarycoll ectionof(unsorted) points .Inparticular,wemake

useofthe foll owinglemma: Lemma:Consideraconvexpol ygonKinthe planean dapointpthatisexterna ltoK,suchthatthevertices ofKarestored incyclicorderinanar ray.Thenthe twotangentsfromptoK(moreformally,th etwo supportinglinesforKthatpassthrou ghp)caneachbecomputedintimeO(logm),wheremisthe numberofv erti cesofK. Wew illleavethep roofofthislemm aasanexer cise,butthekeyideaisthat,sincetheverticesofthehullform acyclicallysortedsequence,itispossibletoadaptbinarysearchtofindthede siredp ointsoftange ncywith p (Fig.17(b)).U singtheabovelemm a,itfollowstha tweca ncomputethetangent from anarbitr arypointtoa singlemini-hullin timeO(logh " )=O(logh). Thefinal "rest rictedalgorithm"(sinceweassumewehave theestimateh " )ispresentedinthecodeblockbelow.

(Thekthstag eisillustratedinFig .17 (c).)Sincewedono tge nerallykn owwhatthevalueo fhis,itis possib le

thatourrestricte dalgorithmmayb erunwithavalueof h " thatisnotwith inthe prescribedrang e,h"h " "h 2 .

LectureNotes17CMSC754

q 1 q 2 q 3 q 4 p k p k!1 Jarvis'salgorithm onmini-hulls kthstageof Jarvis'salgorithm (a)(c)(a)(b) binary search p K tangent Fig.17:Using Jarvi s'salgorithmt omergethemini-hulls. (Inpa rticular,ourfinalalgorithmwillm aintainthegua ranteethath " "h 2 ,butthelowerboundofhmaynot hold.)Ifh " Chan'sAlgorithmfortheR estrictedHullProblem

RestrictedHull(P,h

" ): (1)Let r#!n/h " ". (2)Partition Pintodisjoin tsubsetsP1,P2,...,Pr,e achofsizeatmo sth " . (3)For (i#1tor) computeHull(Pi)usingGraham's scanandstoretheverticesinano rderedarray. (4)Let p0#(&*,0)andletp1betheb ottommos tpointofP. (5)For (k#1toh " ) (a)For(i#1tor) computepointtangentqi+Hull(Pi),tha tis,theverte xofHull (Pi)thatmaximize stheangle!p k#1 p k qi. (b)Let p k+1 bethep ointq+{q1,...,qr}thatmaximiz estheangle!p k#1 p k q. (c)Ifp k+1 #p1thenreturn 'p1,...,p k ((success). (6)(Unable tocompletethehullafterh " iterations.)Return"Failure:h " istoo small." Theupshot softhisare:(1) theJ arvisphasenever performsformore thanh " stages,and(2)ifh"h " ,the algorithmsucceedsinfindingthehull .Toanalyzei tsrunnin gtime,recallthateachpartitionhasroughlyh " points,andsotherear eroughl yn/h " mini-hulls.EachtangentcomputationtakesO(logh " )time,and soeach stagetakesato talofO((n/h " )logh " )time.By(1 )thenumb erofJarv isstagesis atmosth " ,sothetotal runningtimeoftheJarvisp haseisO(h " (n/h " )logh " )=O(nlogh " ). Combiningthiswit hthefactthatthe GrahamphasetakesO(nlogh " )time,theto taltimeofth erestricted algorithmisO(nlogh " ).Ifwemaintaintheconditionthath " "h 2 then,irrespective ofsuccessorfailure,the runningtimewillbeO(nlogh). GuessingtheHull'sSize: Theonl yquestionr emainingishowdoweknowwhat valuetogivetoh " ?Rememberthat, ifh " )h,thealgorithmwillsucceedincomputingthehull,andifh " "h 2 ,therunningtimeoftherestricted algorithmisO(nlogh).Clearlywedonotwanttotryavalueofh " thatiswayto ohig h,orwearedo omedto havinganexcessiv elyhi ghrunningtime.So,weshouldstartourguess small,andw orkuptolargervalues until

LectureNotes18CMSC754

weachiev esuccess.Eachtimewetr yatestvalueh " Asas tart,we couldtryh " =1,2,3,...,i,untilweluckoutassoonash " =h.Unfortunately,thiswouldtake waytool ong.(Con vinceyourselfth atthiswouldresultinatotaltimeof O(nhlogh),whichisevenworsethan

Jarvis'smarch.)

Thenext ideawouldbe toperform adoublingsearch.Thatis,let'stryh " =1,2,4,8,...,2 i .Wh enwefirst succeed,wemighthaveoversh ottheva lueofh,butnotbymorethanafactorof2,thatish"h " "2h.The convexhullwillhave atleastthr eepoints,andclear lyforh)3,wehave2h"h 2 .Thus,thisvalueofh "

willsatis fyourrequirements.Unfortunately,it turnsout thatthisisstilltoo slow.(You shou ldd otheana lysis

yourselfandconvinceyourself thati twillresult inarunningti meofO(nlog 2 h).Betterbutstillnotthebest.) Soif doublingisnot fastenough,whatisnext ?Recallthat weareallowed toovershoottheactualv alueof hbyasmuch ash 2 .Therefore,let'stryrepeatedlysquaringthepreviousguess.Ino ther words,let'stry h " =2,4,16,...,2 2 i .Clearly,assoonaswereachavalueforwhichtherestrictedalgorithmsucceeds,wehave h"h " "h 2 .Therefore,therunningtimeforthisstagewillbeO(nlogh).Butwhataboutthetotaltimefor allthepr eviousstages ?

Toan alyzethetotaltime,co nsiderthe ithguess,h

" i =2 2 i .TheithtrialtakestimeO(nlogh " i )=O ! nlog2 2 i " = O(n2 i ).Weknowthatwewillsucceedassoonash " i )h,thatisifi=*lglgh+.(Throughoutthesemester, wewillus elgtode notelogarithmbase2an dlogwhenthebas edoesnot matter. 4 )Thus,thealgorithm'stotal runningtime(uptoconsta ntfacto rs)is

T(n,h)=

lglgh ' i=1 n2 i =n lglg h ' i=1 2 i . Thisisageomet ricseri es.Let ususethewellknownfact that ( k i=0 2 i =2 k+1 !1.Weobtainatotalrunning timeof

T(n,h)
1+lglgh
=n·2·2 lglgh =2nlgh=O(nlogh), whichis justwhat wewant.Inother words ,bythe "miracle"ofthegeome tricseries,thetotaltimetotryallth e
previousfailedguessesi sasymptoticallythes ameasthetimefor thefinalsuccessf ulguess .Thefinal algorithm
ispre sentedinthecodeblockbelo w.
Chan'sCompleteConvex HullAlgorithm

Hull(P):
(1)h " #2.L#fail. (2)while(L,=fail) (a)Leth " #min((h " ) 2 ,n). (b)L#RestrictedHull(P,h " ). (3)ReturnL.
LowerBound(Opti onal): Nextwewillsho wthatChan' sres ultisasymptoticallyoptimalin thesenset hatanyalgo-
rithmforc omputing theconvexhullofnpointswithhpointsonthehullr equires "(nlogh)time.Thep roofis ageneralizationoftheproofthatsortingasetofnnumbersrequir es"(nlogn)comparisons. Ifyo urecallthepro ofthatsortingtakes atleast "(nlogn)comparisons,itisbasedonthei deathatanys orting algorithmcanbedescribedint ermsof adecisiontree.Eachcomparisonhasatmost3outcomes(<,=,or>). Eachsuch comparisoncorr espondstoaninternalnodei nthetree.Theexe cutionofana lgorithmcanbeviewed asat rav ersalalongapathintheresulting3-ar ytree.Thehe ightofthetre eisalower boundo ntheworst-c ase runningtimeofthealgorith m.There areatle astn!differentpossibleinputs, eachofwhichmustbereordered 4
Whenlognappearsasafactorwithi nasymp tot icbig-Onotation,th ebaseo fthelo garithmdo esnotmatterprovideditisacon stant.Thisis
becauselog a n=log b n/log b a.Thus,changingthebaseonlyalterstheconstantfactor.
LectureNotes19CMSC754
differently,andsoyouhavea3-arytreewi that leastn!leaves.Anysuchtreemusth ave"(log 3 (n!))height. UsingStirling'sappr oximationforn!,thissolvesto"(nlogn)height.(Forfurt herdetails,seet healgorithms bookbyCor men,Lei serson,Riv est,andStein.) Wewi llgivean"(nlogh)lowerboundfo rtheconvexhullprob lem.Infa ct,wewillgi vean"(nlogh)lower boundont hefol lowingsi mplerdecisionproblem,whoseoutputis eitheryesorno. ConvexHullSizeVerificationPr oblem(CHSV) :GivenapointsetPandint egerh,doestheconvexhullof
Phavehdistinctvertices?
Clearlyifthistakes "(nlogh)time,thenc omputingthehu llmusttakeatleastaslong. Aswithsortin g,we willas sumethatthecomputationisdescribed inthef ormof adecisiontree.Thesorts ofdecisionsthata typicalconvexhulla lgorithmwillmakewilllikelyinvolve orientationprimitives.Let'sbe evenmoregeneral, byass umingthatthealgorithmi sallowedt ocomputeanyalgebraicfunctionofthe inputcoordinates.(Thiswil l certainlybepowerfulenoughtoincl udeall theconvexhullalgorithmswehavediscu ssed.) Theresultiscalled analgebraicdecisiontree. Theinput totheCHSVpr oblemisas equenceof2n=Nrealnumbe rs.Wecanthinkofthesenumb ers asfor mingavectorinrealN-dimensionalspace,thatis,(z 1 ,z 2 ,...,z N )=#z(R N ,whichwewillcalla configuration.Eachnodeofthedecisiontreeisassociatedwithamultivariatealgeb raicformulaofdegreeat mostd,wheredisan yfixedconsta nt.Forexample, f(#z)=z 1 z 4 !2z 3 z 6 +5z 2 6 , wouldbeanalg ebraic functi onofdegree2.Thenodebranche sinon eofthreeway s,depen dingonwheth er
theresult isnegative, zero ,orpositive.Eachleafoftheresultingtreecorresp ondstoa possibleanswerthatthe
algorithmmightgive. Foreach inputvector#ztothe CHSVprob lem,theansweris either"yes"or"no" .Thesetofall"yes"points isjust asubseto fpo intsY,R N ,thatisaregioninthisspace.Givenanarbitraryinput#zthepurpo seofthe decisiontreeistot elluswhetherthispoi ntisin Yornot. Thisisdoneby walkingdown thetree,e val uating
thefunctio nson#zandfol lowingtheappropriatebranchesuntilarr ivingata leaf,whichis eitherlabeled "yes"
(meaning#z(Y)or"no".Anabstractexample(notfortheconvexhullproblem)of are gionofconfigur ation
spaceandapossible algebraicdec isiontre e(ofdegree1)is showninthefollowing figu re.(Weha vesimplified
itby makingita binarytree.)Inthisca sethe inpu tisjustapairofrealnumber s. 1 2 3 4 5 6 no Y Y no no no no Y Y 1 2 3 4 5 6 Y Y
Theset

Hierarchicalpartition

Decisiontree
(a)(b)(c) Fig.18:Thegeometr ic inter pretationofanalgebraicdeci siontree. Wesa ythattwo points#u,#v(Yareinthe sameconnectedcomponentofYifthe reisapathinR N from#uto # vsuchthatallth epointsalong thepatha reinthese tY.(Therearetwoconnectedcomponentsinthefigure.)
Wewi llmakeuseoft hefollowing fundament alresu ltonalge braicdecisio ntrees,duetoBen-Or.In tuitively,it
statesthatifyo ursethasMconnectedcomponents,t hentheremustbeatl eastMleavesinanydecisiontre e fortheset, andthe treemusth aveheighta tleastthe logarithmoft henumberof leaves.
LectureNotes20CMSC754

Theorem:LetY(R
N beany setandlet Tbeany d-thord eralgebraicdecisio ntreethatdeterminesmemb er- shipinW.IfWhasMdisjointconnectedcomponents,thenTmusthaveheight atleast"((logM)!N).
Wewi llbeginourp roofwithasimple rproblem .
MultisetSizeVerificati onProblem(MS V):Givenamultisetofnrealnumbers andanintegerk,confirmthat themultiset hasexactlykdistinctelements. Lemma:TheMSVpr oblemr equires"(nlogk)stepsintheworst case inthed-thord eralgebraicdecisio ntree
Proof:Interm sofpointsinR
n ,thesetofpointsforwhichtheansweris"yes"is Y={(z 1 ,z 2 ,...,z n )(R n :|{z 1 ,z 2 ,...,z n }|=k}.
Itsuf ficestoshowthatthereareat least k!k
n!k differentconnectedcomponentsinthiss et,becauseby Ben-Or'sresultitwoul dfollowthatthet imetotes tmembershipinYwouldbe " (log(k!k n!k )!n)="(klogk+(n!k)logk!n)="(nlogk).
Considertheallthetuples(z
1 ,...,z n )withz 1 ,...z k settothedistinctintegersfrom1tok,andz k+1 ...z n eachset toanarbit raryinte gerin thesamerange.Clearlytherearek!waystosele ctthefi rstkelements andk n!k waystosel ectthe remainingelements. Eachsuch tuplehasexactlykdistinctitems,butitis nothard toseet hatifweatt empttocontinuous lymodifyone ofthesetuplestoequalanotherone,we mustchangethenumber ofdistinct elements,implying thateachof these tuplesisinadi fferentconnected componentofY. Tofin ishthelowerboun dproof,w earguethatanyin stanceofMSVcanbe reducedt othe convexhull size verificationproblem(CHSV).Thusa nylowerboundforMSVpro blemappliest oCHSVaswell. Theorem:TheCHSVpr oblemr equires"(nlogh)timetoso lve.
Proof:LetZ=(z
1 ,...,z n )andkbean inst anceoftheMSVproblem.Wecreat eapoi ntset{p 1 ,...,p n } inth eplanewh erep i =(z i ,z 2 i ),andseth=k.(Observethatthepointslieonaparabola,sothatall thepoints areontheconve xhull.)Now ,ifthemultise tZhasexact lykdistinctelements,thentherear e exactlyh=kpointsinthepoi ntset(si ncetheothers arealldupli catesofthese)andsothereareexactly hpointsonthehull. Conver sely,if therearehpointsontheconve xhull ,thenthere wereexactlyh=k distinctnumbersinthemultis ettobegin within Z. Thus,wecannotsol veCHSV anyf asterthan"(nlogh)time,foroth erwisewecou ldsolveMSVinthe sametime. Theproof israther unsatisfyi ng,becauseitrelies onthefactt hatthereare manyduplicatepoints .Youmight
wonder,doesthelower boundstillh oldifther earenoduplicates?Kirkpatri candSeidelactuallyproveastronger
(butharder)re sultthatthe"(nlogh)lowerbound holdsevenyouassumeth atthepointsared istinct.
Lecture5:LineSegmentInte rse ction

Geometricintersections :Oneofthe mostbas icproblems incomputationalgeometryist hatofcomput ingi ntersec-
tions.Intersection computationin2-and3-spac eiscentraltomanydifferentapplicationareas. •Insolid modeling complexshapesareconstruc tedbyapplyingvariousbooleanoperations(intersection, union,anddiff erence)t osimpleprimitiveshapes .Theprocessiscall edconstructivesolidgeometry(CSG). Computingintersecti onsofmodelsurfacesisanessentialpartofthepr ocess.
•Inro boticsandmotionplann ingitisimportan ttoknowwhent woob jectsintersectforcollisiondetection
andcollisionavoidance.
LectureNotes21CMSC754
•Inge ographicinformationsystemsitisoftenusefu ltooverlaytwosubdi visions(e.g.aroadnetworkand countyboundariest odeterminewhereroad maintenanceres ponsibilitieslie).Sincethesenetworksare formedfromcollection soflinese gments,thisgeneratesaproblemofdeterminin gintersectio nsofline segments. •Inco mputergraphics,rayshoo tingisan importantme thodforrenderingscen es.Thecomputationally mostintensive partofrayshootingisdeterminingtheinter sectionoftheraywith otherob jects. Linesegmentint ersection:Theprobl emthatwewillconsi deris,giv ena setSofnlinesegmen tsintheplane, report(thatis,outpu t)allpointswh ere apairoflinesegmentsinters ect.Weassumethateachlinesegmenti s representedbygivingthecoordin atesof itstwoendpoints. Observethatnlinesegmen tscanintersectinasfewa szeroanda smanyas ! n 2 " =O(n 2 )differentintersection points.Wecouldsettl eforanO(n 2 )timealg orithm,claimingthatitiswo rst-caseasymptoticallyop timal,butit
wouldnotbever yusefulin pract ice,sinceinm anyinstancesofint ersectionproblemsintersectionsmayberare.
Therefore,itseemsreasonabl etodesign anoutputsensi tivealgorithm,thatis,onewhoserunningtimedepends notonly ontheinputs ize,b utalsoont heoutputsi ze. GivenasetSofnlinesegmen ts,letI=I(S)denotethenumber ofintersect ions. Wewi llexpresstherunning timeof ouralgo rithmintermsofbo thnandI.Asusual,wewillassumethatthelinesegmentsareingeneral position.Inparticular,weas sume: (1)Thex-coordinatesoftheendpointsandinte rsectionp ointsarea lldistin ct.(Thisimpliesthatn oline segmentisvertical.) (2)Iftwose gme ntsintersec t,thentheyintersectinasingl epoint.(Theyarenotcollinear.) (3)Nothre elinesegm entsintersectin acomm onpoint.
Generalizingthealgorithmto handledegener aciesefficientlyisa ninte restingexe rcise.(Seeourbookfo rmore
discussionofthis.) PlaneSweepAlgorit hm:Letusno wconsi derthealgori thmforreporti ngthesegment intersections.LetS= {s 1 ,...,s n }denotetheli nesegmentswhos eintersectionswe wishtocompute.Themethod,cal ledplane sweep,isafundamentaltechniqueincomputationalgeometry.Wesolvea2-dimensional problem bysimulating theproce ssofsweepinga1-dimension allinea crosstheplane.Thei nters ectionsofthesweeplinewiththeseg- mentsdefinesa collectionofpoints alongthes weepline.W ewillstore thesepoin tsinadatastructu re,which wecallthe sweep-linestatus. Althoughwe mightvisualize thesweeping processasacontin uousone,t herei sadiscreteset ofeventpoints whereimportantthingshappen. Asthelinesweepsf romlef ttoright,pointsareinserted,deleted,andmay swaporderalo ngthesweepline.T hus,wereducea static2-dimensionalproblemto adynamic1-dimensional problem. Therearethr eebasicelement sthataremaintained atanytimeinanyplane-sweepalgorithm:(1)thepartial
solutionthathasalre adybeenco nstructedtothe leftofthesweepline,(2)the currentstatuso fobjects alongthe
sweeplineitself,and (3)a(sub)se tofthefu tureeventsto beprocessed(seeFig.19). Theke ytodesigninganef ficientplane-sweep algorithminvolvesdetermining thebestwaytostoreandupd ate
thesethreeeleme ntsaseachn eweventisprocess.L et'scon sidereacho ftheseelementsingre aterdeta ilinthe
contextofline-s egmenti ntersection.
Sweepli nestatus:Wewi llsimulatet hesweepingofaverticalli ne"fromleftto right.The swee p-linestatuswill
consistofthelinese gmentst hatintersect thesweeplines orted,say,fromto ptobottom.Ino rdertom aintain thissetdy namically, wewillstoretheminadatastructure,whichwillbe described below.
Notethateach timethes weeplinemo ves, allthey-coordinatesoftheintersectionpointsch angeas well.Itw ill

betoo inefficientto continuallyupdateallthe y-coordinateseachtimethesweeplinemo ves.Weexploitth efact
thatitisnot thea ctua ly-coordinatesthatwereallycareabout, justtheirorder.Todothis,ratherthanstoring
LectureNotes22CMSC754
futureeven tpoint discoveredintersection ! sweepline
Fig.19:Planes weep.
y-coordinates,foreachlinesegments i thatintersects thesweepline,westoretheco efficien ts(a i ,b i )ofthe equationoftheline, e.g., y=a i x+b i .(Thesecoefficientscaneasilybederivedfromthesegmentendpoints.) Inthis way,w henevertheswee plinearrivesatanewx-coordinate,sayx=x 0 ,wecandeterminethecurrent y-coordinateatwhichsegments i intersectsthesweeplineas y(x 0 )=a i x 0 +b i (seeFig.2 0).Asweshall see, onlyaconst antnumberof suchintersections needto beev aluatedateachev entpoi nt. ! (a 2 ,b 2 ) s 2 s 1 (a 1 ,b 1 ) y 1 (x 0 )=a 1 x 0 +b 1 y 2 (x 0 )=a 2 x 0 +b 2 x=x 0
Fig.20:Thesweep- line stat usstorescoefficientsoftheli neequations,andthey-coordinatesoftheintersectionsare
computedasneeded. EventsandDetectingI ntersect ions:Itsu fficestoprocesseventson lywh enthereisachangein thesweep-line status.Thesex-coordinatesarecalledeventpoints.Forourapplication,wehavethreetypesofeventpoints, correspondingtowhenthesweepline encounters(1)t hel eftendpointofase gment,( 2)the rightendpointofa segment,and(3)anintersectio npointbetw eentwose gments. Notethatendpoint events canbepr esortedbeforethes weepruns.Incontr ast,inter sectioneventswillbe
discoveredasthesweepexecutes.I tis importantthat eacheventbedet ectedb eforetheactualeventoccur s.Our
strategywillbeasfollows .Whenevertwol ineseg ments becomeadjacentalongthesweep line,wewil lcheck whetherthe yhaveaninter sectionoccurringtotheright ofthesweep line.Ifs o,wewilladdthis newevent toa priorityqueueoffutureevent

Politique de confidentialité -Privacy policy