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
Computational Geometry Exercise 1 Exercise 2 a1 3 http://www ti inf ethz ch/ew/courses/CG10/ 3 S1 a2 Exercise 3
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)
These lecture notes are designed to accompany a course on “Computational Geometry” three hours of lecture and two hours of exercises each week
The exercises below are intended to provide a means to test your understanding of the programming-related material covered in the course
https://cw felk cvut cz/doku php/courses/a4m39vg/start What is Computational Geometry (CG)? CG Solves geometric problems that require clever
19 oct 2015 · Course Information Lecture Slides Exercises Additional Material Computational Geometry in Computer Science Master's Studies
This course is about Computational geometry (theory): Study of geometric problems on geometric data, and how efficient algorithms that solve them can be
14 avr 2001 · Computational geometry is concerned with the algorithmic study of elemen- tary geometric problems Ever since its emergence as a new branch
algorithms to computational geometry 1 Geometric analogues of classical graph algorithm problems Typical issue: using geometric information
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls TamaraMchedlidzeDarrenStrashComputationalGeometry LectureINSTITUTF
URTHEORETISCHE INFORMATIK FAKULTATF URINF ORMATIKIntroduction&ConvexHulls 19.10.20151Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls AlgoGeom-TeamLecturersExerciseLeader BenjaminNiedermann
benjamin.niedermann@kit.eduDr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls OrganizationWebsitehttp://i11www.iti.kit.edu/teaching/winter2015/compgeom/CourseInfo rmation
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls OrganizationExercises
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls ComputationalGeometry Objectives:Attheendof thecourse youwill beable to...explainconcepts, structures,andp roblemdenitions
understandthe discussedalgorithms, andexplainand analyzethem selecta ndadaptappropriatea lgorithmsand datastructuresanalyzenew geometricproblems anddevelopecient solutionsCourseTime Breakdown:Timein lecturesandexercise sessions
Examp reparationca.35h 5LP= 150hca.25h ca.20h ca.40h ca.30h PriorKnowledge:AlgorithmsandElementa ryGeometry5
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls ModulesandGradingMaster'sin ComputerScienceComputationalGeometry (IN4INAG)[5 LP]
ComputerGraphics Algorithms(IN4INA CG)[3LP]TestModalities Semester-longp rojectinsmallteams(application-driven
geometricalgo rithms) !20%of gradeOneo ralexamination(about20m inutes) !80%of gradeMoreonthisin 1{2weeks 6Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls ClassMater ialsRolfKlein:
http://www.cs.umd.edu/class/spring2012/cmsc754/Lects/cmsc754-lects.pdfPDFavailable onspringerlink.com! 7
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Whatis ComputationalGeometry?
Whereis ComputationalGeometryUsed? ComputerGraphics andImagePro cessingDr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Example1 ?It'sa hot42
Csummer dayin Karlsruhe.Supposeyou know thelo cationofeveryicecreamshop inthecit y.Ho wcany ou determinethe closesticecream shopfor anylocation ona map?!Thesolution isadivisionofR2,called aVoronoiDiagram. Manyapplications, including:siteplanning, nearest-n eighb or nding,rob otmotionplanning,radiocells ... 9Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Example2 Nowitis50
Cin Karlsruhe.W ewanttosenda robottobuy anice creamcone.Ho wcanthe robotreach thedestination withoutpassing throughhouses,pa rkbenches ,andtrees? Motionplanning problemin robotics: Givena setofobstacles withasta rtanddestination point,nd acollision-free shortestroute (e.g.,usingthevisibilitygraph).10Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Example3 Mapsin geographicinformation systemsconsistof several
levels(e.g., roads,water, bord ers,etc.).When superimposing severalla yers,whataretheintersectionpoin ts? Oneexample istoto viewallr oadsandrivers asaset oflinks andask forthe bridges.Forthese, youhave tondall intersectionsb etweenthetwolayers.Testingalledgepairs is slow.Howcan you quicklynd all intersections?11Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Example4 Givena mapanda querypoint q(e.g.,a mouseclick),
determinethe countrycontainingq. Wewantafast datastructurefo ranswering pointqueries. 12Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Example5
Anavigation systemshoulddispla yacurrent map.How canwe eectivelycho osethedatatodisplay? Evaluatingeach mapfeatureis unrealistic. Wewantafast datastructurefo ranswering rangequeries 13Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls TopicsWewillcoverthe followi ngtopics:
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls ConvexHulls 15
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls MixingRatios :1:2:3:4:4:3:2:1BAs
1s 2s 3q 2qDr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Denitionof ConvexHullDef:Aregion SR2iscalled convex,when fort wopoints
p;q2Sthenline pq2S.Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls AlgorithmicApproachLemma:Forasetofpoints PR2,CH(P)is
aconvex polygonthat containsPandwhosevertice sareinP.Input:Aset ofpoints P=fp1;:::;pngOutput:Listof verticesofCH(P)inclo ckwiseorderObservation:(p;q)isan edgeofCH(P),eachp ointr2Pnf p;qgstrictlyright oftheo rientedline
!pqoronthe linesegmentpqpq ! pq18Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls AFirst Algorithm FirstConvexHull(P)
E ; foreach(p;q)2PPwithp6=qdovalid trueforeachr2Pdoifnot (rstrictlyright of !pqorr2pq)thenvalid falseifvalidthenE E[f (p;q)gconstructso rtednodelistLofCH(P)fromE
returnLCheckall possible edges(p;q)TestinO(1)timew ithx ryr1 x pyp1 x qyq1 <0!Exercise!19Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls RunningTime AnalysisFirstConvexHull(P)
E ; foreach(p;q)2PPwithp6=qdovalid trueforeachr2Pdoifnot (rstrictlyright of !pqorr2pq)thenvalid falseifvalidthenE E[f (p;q)gconstructso rtednodelistLofCH(P)fromE
returnL(1)(n)(n2 n)(n3)O(n2)Lemma:Theconvex hullofnpointsintheplane canbe computedin O(n3)time.20Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls IncrementalApp roachIdea:Fori=1 ;:::;ncomputeCH(Pi)wherePi=fp1;:::;pigQuestion:Whicho rderingofthepointsisuseful?Answer:Fromlefttoright! lowerhullupperhullConsiderthe upp erand lowerhull separatelyUpperConvexHull(P)
hp1;p2;:::;pni sortPfromleft torightwhilejLj>2andthelast 3points inLdonot formright turndoremovethe second-to-lastpoint inLreturnLlowerhullishandledsimilarly!21
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls RunningTime AnalysisUpperConvexHull(P)
hp1;p2;:::;pni sortPfromright toleftwhilejLj>2andlast3 pointsin Ldonot formright turndoremovethe second-to-lastpoint fromLreturnLO(nlogn)(n 2)?AmortizedAnalysisEachp ointisinsertedintoLexactlyonce Ap ointinLisremoved atmostonce fromL)Runningtime oftheforloopincludingthewhileloopisO(n)O(n)Theorem1:Theconvex hullofnpointsintheplane canbe
computedin O(nlogn)time.!Graham'sScan .22Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls AlternativeApp roach:GiftWrappingIdea:Beginwith apoint p1ofCH(P),then ndthenext edgeof
ifpj+1=p1thenbreakelsej j+1 return(p1;:::;pj+1)O(n)O(h)O(n)O(nh)Theorem2:Theconvex hullCH(P)ofnpointsPinR2can
becomputedinO(nh)timeusing GiftW rapping (alsocalled Jarvis'March),where h=jCH(P)j.!moreonthatin theexercises!23Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls ComparisonWhichalgo rithmisbetter?Graham'sScan: O(nlogn)timeJarvis'March:O(nh)timeItdep endsonhowlarge CH(P)is!Idea:Combinethe two approachesintoanoptimalalgorithm!24
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Chan'sAlgo rithmSupposewekno wh:GiftW rappingGrahamScanChanHull(P,h)
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Examplen= 16GrahamScan26
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Examplen= 16GrahamScanGiftW rapping26
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Examplen= 16GrahamScanGiftW rapping26
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Chan'sAlgo rithmO(logh)!Exercise!Supposewekno wh:ChanHull(P,h)
j+1 argmaxf\pj 1pjqjq2f q1;:::;qdn=heggreturn(p1;:::;ph)O(hlogh)O(n=h)O(nlogh)O(h)O (n=h)= O(n)O(nlogh)Total:O(nlogh)27
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Chan'sAlgo rithmO(mlogm)O(n=m)O(nlogm)O(nlogm)O(logm)O(m)O (n=m)= O(n)ChanHull(P,m)
Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Whatto dowithm?FullChanHull(P)
fort=0 ;1;2;:::dom= minfn;22tg result ChanHull(P,m) ifresult6=failurethenbreakreturnresultRunningtime: O(nlogm)=Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Whatto dowithm?FullChanHull(P)
fort=0 ;1;2;:::dom= minfn;22tg result ChanHull(P,m) ifresult6=failurethenbreakreturnresultTheorem3:Theconvex hullCH(P)ofnpointsPinR2can becomputedinO(nlogh)timewith Chan'sDr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls DiscussionIsit possibleto computefasterthanO(nlogn)orO(nlogh)time?Generallynot! Analgorithm tocomputethe convexhullcanalso sort
(exercise!))lowerbound(nlogn).Whathapp ensinGraham'sScanwhenso rtingPisnot unique?Uselexico graphicorder!Whathapp enswithcollinearp ointsinCH(P)?Graham:F ormsnorightturn,soaninte rior pointis deleted.
Jarvis:Choose farthestpointWhatab outtherobustnessofthealgo rithms?Regardingrobustness:imp recisionof
oating-pointarithmeticDr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls DesigningGeometric Algorithms{Guidelines1.)Eliminate degeneratecases( !generalp osition)uniquex-coordinatesnothree collinearp oints
:::2.)Adjust degenerateinputs integrateinto existingsolutions (e.g.,compute lexicographicorder ifx-coordinatesarenot unique)mayrequiresp ecialtreament3.)Implementation primitiveoperations(availab leinlibraries?) robustness31