[PDF] Computational Geometry · Lecture Introduction & Convex Hulls




Loading...







[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

[PDF] Computational Geometry · Lecture Introduction & Convex Hulls 58795_6algogeom_ws15_vl01_printable.pdf

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls TamaraMchedlidzeDarrenStrashComputationalGeometry LectureINSTITUTF

URTHEORETISCHE INFORMATIK FAKULTATF URINF ORMATIKIntroduction&ConvexHulls 19.10.20151

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls AlgoGeom-TeamLecturersExerciseLeader BenjaminNiedermann

benjamin.niedermann@kit.edu

Room309

Ocehours: byapp ointmentScheduleLecture:Mon. 15:45{17:15, SR301 Exercises:W ed.15:45{17:15,SR301 (startingOct. 28)TamaraMchedlidze mched@iti.uka.de

Room307

Ocehours: by

appointment

DarrenStrash

strash@kit.edu

Room206

Ocehours: by

appointment 2

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls OrganizationWebsitehttp://i11www.iti.kit.edu/teaching/winter2015/compgeom/CourseInfo rmation

LectureSlides

Exercises

AdditionalMaterial ComputationalGeometry inComputerScience Master's StudiesAlgorithms1+2TheoreticalBasi csBachelorMasterAlgorithmdesign,theor etic al basics,computer graphicsComputationalGeometry. ..AlgorithmsforPlana rGraphs3

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls OrganizationExercises

Everysec ondWednesdaystarting28.10

Exercisep roblemspostedatleastone weekbeforean

exercisesession. Rinforcelecturematerial,help prepare forexam. Whatwill theexercisesinvol ve?

Weeklywork forabout45{60minutes

Activepa rticipationinexercisesisexpected

Volunteerswillwo rkproblems ontheboard

Canhand inexercisesfo rfeedback

Variationswillbeannounced

Exerciseon 16.12insteadof 23.124

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls ComputationalGeometry Objectives:Attheendof thecourse youwill beable to...explainconcepts, structures,andp roblemde nitions

understandthe discussedalgorithms, andexplainand analyzethem selecta ndadaptappropriatea lgorithmsand datastructures

analyzenew geometricproblems anddevelopecient solutionsCourseTime Breakdown:Timein lecturesandexercise sessions

Preparationandreview

Workingonexercises

Projectw ork

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]

AlgorithmEngineerin g&Applications(IN4INAEA)[5LP]

Designand AnalysisofAlgo rithms(IN4INDAA) [5LP]

ComputerGraphics Algorithms(IN4INA CG)[3LP]TestModalities Semester-longp rojectinsmallteams(application-driven

geometricalgo rithms) !20%of gradeOneo ralexamination(about20m inutes) !80%of gradeMoreonthisin 1{2weeks 6

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls ClassMater ialsRolfKlein:

AlgorithmischeGeometrie

Springer,2ndEdition,2005

M.de Berg,O.Cheong, M.vanKreveld, M.Overmars:

ComputationalGeometry: AlgorithmsandApplications

Springer,3rdEdition,2008 Bothb ooksareavailableinthelibra ry!

DavidMount:

ComputationalGeometry

LectureNotes CMSC754,U. Maryland,2012

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 cessing

Visualization

GeographicInfo rmationSystems(GIS)

Robotics

...CentralThemes Geometricalgo rithmsanddatastructures Discreteand combinatorialgeometric problemsComputationalgeometry isab ranchof computerscience that dealswith algorithmicsolutions togeometricproblems.A centralp roblemisthestorageandpro cessingofgeometric data...suchas points,lines, circles,polygons...8

Dr.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 ... 9

Dr.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).10

Dr.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 to ndall intersectionsb etweenthetwolayers.Testingalledgepairs is slow.Howcan you quickly nd all intersections?11

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Example4 Givena mapanda querypoint q(e.g.,a mouseclick),

determinethe countrycontainingq. Wewantafast datastructurefo ranswering pointqueries. 12

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls Example5

Anavigation systemshoulddispla yacurrent map.How canwe e ectivelycho osethedatatodisplay? Evaluatingeach mapfeatureis unrealistic. Wewantafast datastructurefo ranswering rangequeries 13

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls TopicsWewillcoverthe followi ngtopics:

ConvexHulls

LineSegment Intersection

PolygonTriangulation

GeometricLinea rProgramming

DataStructures forRange Queries

DataStructure forP ointLocationQueries

VoronoiDiagramsandDelaunayT riangulation

DualityofPoints andLines

Quadtrees

Well-SeparatedPairDecompositions

VisibilityGraphs

...14

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 2q

1Obs:Givena setSR2ofmixtures, wecan makeanother

mixtureq2R2outof S,q2convexhull CH(S).ddGiven...MixturefractionAfractionBs

110%35%

s

220%5%

s

340%25%MixturAnteil AAnteilBq

115%20%

q

225%28%canw emixusings1,s2,s3?geom.interp retationq=P

iisiwithP ii=1 .16

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls De nitionof ConvexHullDef:Aregion SR2iscalled convex,when fort wopoints

p;q2Sthenline pq2S.

Theconvexhull CH(S)ofSisthe smallestconvex

regioncontaining S.Inphysics: puta largerubb erband aroundallpoints andlet itgo!unfortunately,doesnothe lp algorithmicallyInmathematics: de neCH(S)= \

CS:CconvexCdoesnothelp:-( 17

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls AlgorithmicApproachLemma:Forasetofpoints PR2,CH(P)is

aconvex polygonthat containsPand

whosevertice 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! pq18

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls AFirst Algorithm FirstConvexHull(P)

E ; foreach(p;q)2PPwithp6=qdovalid true

foreachr2Pdoifnot (rstrictlyright of!pqorr2pq)thenvalid falseifvalidthenE E[f (p;q)gconstructso rtednodelistLofCH(P)fromE

returnLCheckall possible edges(p;q)TestinO(1)timew ith x ryr1 x pyp1 x qyq1 <0!Exercise!19

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls RunningTime AnalysisFirstConvexHull(P)

E ; foreach(p;q)2PPwithp6=qdovalid true

foreachr2Pdoifnot (rstrictlyright of!pqorr2pq)thenvalid falseifvalidthenE E[f (p;q)gconstructso rtednodelistLofCH(P)fromE

returnL(1)(n)(n2n)(n3)O(n2)Lemma:Theconvex hullofnpointsintheplane canbe computedin O(n3)time.20

Dr.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 toright

L h p1;p2i

fori 3tondoL.append(pi)

whilejLj>2andthelast 3points inLdonot formright turndoremovethe second-to-lastpoint inLreturnLlowerhullishandledsimilarly!21

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls RunningTime AnalysisUpperConvexHull(P)

hp1;p2;:::;pni sortPfromright toleft

L h p1;p2i

fori 3tondoL.append(pi)

whilejLj>2andlast3 pointsin Ldonot formright turndoremovethe second-to-lastpoint fromLreturnLO(nlogn)(n2)?AmortizedAnalysisEachp ointisinsertedintoLexactlyonce Ap ointinLisremoved atmostonce fromL)Runningtime oftheforloopincludingthewhileloopisO(n)O(n)Theorem1:Theconvex hullofnpointsintheplane canbe

computedin O(nlogn)time.!Graham'sScan .22

Dr.T amaraMchedlidzeDr.Da rrenStrashComputationalGeometry LectureIntroduction&ConvexHulls AlternativeApp roach:GiftWrappingIdea:Beginwith apoint p1ofCH(P),then ndthenext edgeof

CH(P)inclo ckwiseorder.GiftWrapping(P)

p

1=( x1;y1) rightmostp ointinP;p0 (x1;1);j 1

whiletruedop j+1 argmaxf\pj1;pj;qjq2Pnf pj1;pjgg

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!23

Dr.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)

DividePintosets Piwithhnodes

forifrom1 todn=hedoComputewith GrahamScanCH(Pi)p

1=( x1;y1) rightmostp ointinP

p

0 (x1;1)

forj=1 tohdofori=1 todn=hedoq i argmaxf\pj1pjqjq2Pinf pj1;pjggp j+1 argmaxf\pj1pjqjq2f q1;:::;qdn=heggreturn(p1;:::;ph)25

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)

DividePintosets Piwithhnodes

forifrom1 todn=hedoComputewith GrahamScanCH(Pi)p

1=( x1;y1) rightmostp ointinP

p

0 (x1;1)

forj=1 tohdofori=1 todn=hedoq i argmaxf\pj1pjqjq2Pinf pj1;pjggp

j+1 argmaxf\pj1pjqjq2f 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)

DividePintosets Piwithmnodes

forifrom1 todn=medoComputewith GrahamScanCH(Pi)p

1=( x1;y1) rightmostp ointinP

p

0 (x1;1)

forj=1 tomdofori=1 todn=medoq i argmaxf\pj1pjqjq2Pinf pj1;pjggp j+1 argmaxf\pj1pjqjq2f q1;:::;qdn=megg ifpj+1=p1thenreturn (p1;:::;pj+1)returnfailureButin generalhisunkno wn!Total:O(nlogm)28

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)=

O(nlog22t)dloglogheP

t=0O(nlog22t)=O(n)dloglogheP t=0O(2t)O (n)O (2loglogh)=O(n)O (logh)=O(nlogh)29

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's

Algorithm,whe reh=jCH(P)j.29

Dr.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-pointarithmetic

FirstConvexHullp ossiblyproducesavalid polygon

Grahamand Jarvisalw aysprovideap olygon,butitmayhaveminor defects30

Dr.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
Politique de confidentialité -Privacy policy