Transcription
Computational Geometry · LectureIntroduction & Convex HullsINSTITUT FÜR THEORETISCHE INFORMATIK · FAKULTÄT FÜR INFORMATIKChih-Hung Liu · Tamara Mchedlidze18.4.20181 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
AlgoGeom-TeamLecturers Tamara Mchedlidze mched@iti.uka.de Room 307 Office hours: byappointment2 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry Lecture Chih-Hung Liu chih-hung.liu@inf.ethz.ch ETH Zürich Office hours: byappointmentIntroduction & Convex Hulls
AlgoGeom-TeamLecturers Tamara Mchedlidze mched@iti.uka.de Room 307 Office hours: byappointmentExercise Leader Chih-Hung Liu chih-hung.liu@inf.ethz.ch ETH Zürich Office hours: byappointment Guido Brückner brueckner@kit.edu Room 317 Office hours: by appointment2 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
AlgoGeom-TeamLecturers Tamara Mchedlidze mched@iti.uka.de Room 307 Office hours: byappointmentExercise Leader Chih-Hung Liu chih-hung.liu@inf.ethz.ch ETH Zürich Office hours: byappointment Guido Brückner brueckner@kit.edu Room 317 Office hours: by appointmentSchedule Lecture: Wed. 14:00 – 15:30 SR 301 Exercises: Mon. 15:45 – 17:15, SR 236 (starting ?)2 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
ing/sommer2018/compgeom/ Course Information Lecture Slides Exercises Additional Material3 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
ing/sommer2018/compgeom/ Course Information Lecture Slides Exercises Additional MaterialComputational Geometry in Computer Science Master’sStudiesBachelorMasterAlgorithms 1 2Theoretical BasicsAlgorithms for Planar GraphsComputationalGeometry.Algorithm design, theoreticalbasics, computer graphicsPrior Knowledge: Algorithms and Elementary Geometry3 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
OrganizationExercises Every second Monday starting 27.04 Exercise problems posted at least one week before anexercise session. Reinforce lecture material, help prepare for exam.What will the exercises involve? Independent or group preparation Weekly meetings in class Active participation in class is expected - we expect thatyou present at least one solution on the board Can hand in exercises for feedback4 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Computational GeometryObjectives:At the end of the course you will be able to. explain concepts, structures, and problem definitions understand the discussed algorithms, and explain and analyze them select and adapt appropriate algorithms and data structures analyze new geometric problems and develop efficient solutions5 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Computational GeometryObjectives:At the end of the course you will be able to. explain concepts, structures, and problem definitions understand the discussed algorithms, and explain and analyze them select and adapt appropriate algorithms and data structures analyze new geometric problems and develop efficient solutions5 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Computational GeometryObjectives:At the end of the course you will be able to. explain concepts, structures, and problem definitions understand the discussed algorithms, and explain and analyze them select and adapt appropriate algorithms and data structures analyze new geometric problems and develop efficient solutionsCourse Time Breakdown: Time in lectures and exercise sessions Preparation and review Working on exercises Exam preparation5 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry Lecture5LP 150hca.ca.ca.ca.35h45h30h30hIntroduction & Convex Hulls
Class MaterialsM. de Berg, O. Cheong, M. van Kreveld, M. Overmars:Computational Geometry: Algorithms and ApplicationsSpringer, 3rd Edition, 2008Rolf Klein:Algorithmische GeometrieSpringer, 2nd Edition, 2005David Mount:Computational GeometryLecture Notes CMSC 754, U. Maryland, /Lects/cmsc754-lects.pdfBoth books are available in the library!6 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Class MaterialsM. de Berg, O. Cheong, M. van Kreveld, M. Overmars:Computational Geometry: Algorithms and ApplicationsSpringer, 3rd Edition, 2008PDF available on springerlink.com!Rolf Klein:Algorithmische GeometrieSpringer, 2nd Edition, 2005David Mount:Computational GeometryLecture Notes CMSC 754, U. Maryland, /Lects/cmsc754-lects.pdfBoth books are available in the library!6 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
What is Computational Geometry?7 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
What is Computational Geometry?Computational geometry is a branch of computer science thatdeals with algorithmic solutions to geometric problems. Acentral problem is the storage and processing of geometricdata.such as points, lines, circles, polygons.7 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
What is Computational Geometry?Computational geometry is a branch of computer science thatdeals with algorithmic solutions to geometric problems. Acentral problem is the storage and processing of geometricdata.such as points, lines, circles, polygons.Where is Computational Geometry Used? Computer Graphics and Image Processing Visualization Geographic Information Systems (GIS) Robotics .7 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
What is Computational Geometry?Computational geometry is a branch of computer science thatdeals with algorithmic solutions to geometric problems. Acentral problem is the storage and processing of geometricdata.such as points, lines, circles, polygons.Where is Computational Geometry Used? Computer Graphics and Image Processing Visualization Geographic Information Systems (GIS) Robotics .Central Themes Geometric algorithms and data structures Discrete and combinatorial geometric problems7 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 1It’s a hot 42 C summer day in Karlsruhe. Suppose you knowthe location of every ice cream shop in the city. How can youdetermine the closest ice cream shop for any location on amap?8 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 1It’s a hot 42 C summer day in Karlsruhe. Suppose you knowthe location of every ice cream shop in the city. How can youdetermine the closest ice cream shop for any location on amap?8 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 1It’s a hot 42 C summer day in Karlsruhe. Suppose you knowthe location of every ice cream shop in the city. How can youdetermine the closest ice cream shop for any location on amap?!?8 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 1It’s a hot 42 C summer day in Karlsruhe. Suppose you knowthe location of every ice cream shop in the city. How can youdetermine the closest ice cream shop for any location on amap?!?The solution is a division of R2 , called a Voronoi Diagram.Many applications in Natural sciences, Geometry, Informatics,Health, Engeneering,.8 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 2Now it is 50 C in Karlsruhe. We want to send a robot to buyan ice cream cone. How can the robot reach the destinationwithout passing through houses, park benches, and trees?9 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 2Now it is 50 C in Karlsruhe. We want to send a robot to buyan ice cream cone. How can the robot reach the destinationwithout passing through houses, park benches, and trees?9 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 2Now it is 50 C in Karlsruhe. We want to send a robot to buyan ice cream cone. How can the robot reach the destinationwithout passing through houses, park benches, and trees?Motion planning problem in robotics:Given a set of obstacles with a start and destination point, finda collision-free shortest route (e.g., using the visibility graph).9 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 3Maps in geographic information systems consist of severallevels (e.g., roads, water, borders, etc.). When superimposingseveral layers, what are the intersection points?One example is to view all roads and rivers as a set of linksand ask for the bridges. For these, you have to find allintersections between the two layers.10 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 3Maps in geographic information systems consist of severallevels (e.g., roads, water, borders, etc.). When superimposingseveral layers, what are the intersection points?One example is to view all roads and rivers as a set of linksand ask for the bridges. For these, you have to find allintersections between the two layers.10 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 3Maps in geographic information systems consist of severallevels (e.g., roads, water, borders, etc.). When superimposingseveral layers, what are the intersection points?One example is to view all roads and rivers as a set of linksand ask for the bridges. For these, you have to find allintersections between the two layers.10 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 3Maps in geographic information systems consist of severallevels (e.g., roads, water, borders, etc.). When superimposingseveral layers, what are the intersection points?One example is to view all roads and rivers as a set of linksand ask for the bridges. For these, you have to find allintersections between the two layers.Testing all edge pairs isslow. How can youquickly find allintersections?(Line Segment Intersections)10 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 4Given a map and a query point q (e.g., a mouse click),determine the country containing q.11 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 4Given a map and a query point q (e.g., a mouse click),determine the country containing q.We want a fast data structure for answering point queries.(Point Location)11 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 5A navigation system should display a current map. How can weeffectively choose the data to display?12 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 5A navigation system should display a current map. How can weeffectively choose the data to display?12 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Example 5A navigation system should display a current map. How can weeffectively choose the data to display?Evaluating each map feature is unrealistic.We want a fast data structure for answering range queries12 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
TopicsWe will cover the following topics: Convex Hulls Line Segment Intersection Polygon Triangulation Geometric Linear Programming Data Structures for Range Queries Data Structure for Point Location Queries Voronoi Diagrams and Delaunay Triangulation Duality of Points and Lines Quadtrees Well-Separated Pair Decompositions Visibility Graphs13 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Convex Hulls14 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Mixing RatiosGiven.Mixtures1s2fraction A fraction B10 %35 %20 %5%15 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Mixing RatiosGiven.Mixtures1s2fraction A fraction B10 %35 %20 %5%canwe mixMixtur Anteil A Anteil Bq1q215 %25 %20 %28 %using s1 , s2 ?15 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Mixing RatiosGiven.Mixtures1s2fraction A fraction B10 %35 %20 %5%canwe mixMixtur Anteil A Anteil Bq1q215 %25 %20 %28 %using s1 , s2 ?q1 : Yes! Ratio 1:1q2 : No!15 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Mixing RatiosGiven.Mixtures1s2s3fraction A fraction B10 %35 %20 %5%40 %25 %canwe mixMixtur Anteil A Anteil Bq1q215 %25 %20 %28 %using s1 , s2 , s3 ?15 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Mixing RatiosGiven.Mixtures1s2s3Bfraction A fraction B10 %35 %20 %5%40 %25 %canwe mixMixtur Anteil A Anteil Bq1q215 %25 %20 %28 %.4s1.3s3.2.1s2using s1 , s2 , s3 ?iontaterprtegeom. in15 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry Lecture.1.2.3.4AIntroduction & Convex Hulls
Mixing RatiosGiven.Mixtures1s2s3Bfraction A fraction B10 %35 %20 %5%40 %25 %canwe mixMixtur Anteil A Anteil Bq1q215 %25 %20 %28 %.4s1.3.2q1.1s2using s1 , s2 , s3 ?iontaterprtegeom. in15 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry Lectures3q2.1.2.3.4AIntroduction & Convex Hulls
Mixing RatiosGiven.Mixtures1s2s3Bfraction A fraction B10 %35 %20 %5%40 %25 %canwe mixMixtur Anteil A Anteil Bq1q215 %25 %20 %28 %.4s1.3.2q1.1s2using s1 , s2 , s3 ?iontaterprtegeom. in15 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry Lectures3q2.1.2.3.4AIntroduction & Convex Hulls
Mixing RatiosGiven.Mixtures1s2s3Bfraction A fraction B10 %35 %20 %5%40 %25 %canwe mixMixtur Anteil A Anteil Bq1q215 %25 %20 %28 %.4s1.3.2q1.1s2using s1 , s2 , s3 ?iontaterprtegeom. ins3q2.1.2.3.4AObs: Given a set S R2 of mixtures, we can make anothermixture q R2 out of S 15 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Mixing RatiosGiven.Mixtures1s2s3Bfraction A fraction B10 %35 %20 %5%40 %25 %canwe mixMixtur Anteil A Anteil Bq1q215 %25 %20 %28 %.4s1.3.2q1.1s2using s1 , s2 , s3 ?iontaterprtegeom. ins3q2.1.2.3.4AObs: Given a set S R2 of mixtures, we can make anothermixture q R2 out of S q convex hull CH(S).PPq i λi si with i λi 1.15 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Mixing RatiosGiven.Mixtures1s2s3Bfraction A fraction B10 %35 %20 %5%40 %25 %canwe mixMixtur Anteil A Anteil Bq1q215 %25 %20 %28 %.4s1.3.2q1.1s2using s1 , s2 , s3 ?iontaterprtegeom. ins3q2.1.2.3.4AObs: Given a set S R2d of mixtures, we can make anothermixture q R2d out of S q convex hull CH(S).PPq i λi si with i λi 1.15 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Definition of Convex HullDef: A region S R2 is called convex, when for two pointsp, q S, line pq S.The convex hull CH(S) of S is the smallest convexregion containing S.16 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Definition of Convex HullDef: A region S R2 is called convex, when for two pointsp, q S, line pq S.The convex hull CH(S) of S is the smallest convexregion containing S.16 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Definition of Convex HullDef: A region S R2 is called convex, when for two pointsp, q S, line pq S.The convex hull CH(S) of S is the smallest convexregion containing S.In mathematics: define CH(S) \CC S : C convex16 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Definition of Convex HullDef: A region S R2 is called convex, when for two pointsp, q S, line pq S.The convex hull CH(S) of S is the smallest convexregion containing S.In mathematics: define CH(S) \CC S : C convexIn physics: put a large rubber bandaround all points16 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Definition of Convex HullDef: A region S R2 is called convex, when for two pointsp, q S, line pq S.The convex hull CH(S) of S is the smallest convexregion containing S.In mathematics: define CH(S) \CC S : C convexIn physics: put a large rubber bandaround all points and let it go!16 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Definition of Convex HullDef: A region S R2 is called convex, when for two pointsp, q S, line pq S.The convex hull CH(S) of S is the smallest convexregion containing S.In mathematics: define CH(S) \CC S : C convexIn physics: put a large rubber bandaround all points and let it go!unfortunately none help algorithmically16 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Algorithmic ApproachLemma:For a set of points P R2 , CH(P ) isa convex polygon that contains P andwhose vertices are in P .17 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Algorithmic ApproachLemma:For a set of points P R2 , CH(P ) isa convex polygon that contains P andwhose vertices are in P .Input: A set of points P {p1 , . . . , pn }Output: List of vertices of CH(P ) in clockwise order17 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Algorithmic ApproachLemma: pqpqFor a set of points P R2 , CH(P ) isa convex polygon that contains P andwhose vertices are in P .Input: A set of points P {p1 , . . . , pn }Output: List of vertices of CH(P ) in clockwise orderObservation:(p, q) is an edge of CH(P ) each point r P \ {p, q} strictly right of the oriented line pq or on the line segment pq17 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
A First AlgorithmFirstConvexHull(P )E foreach (p, q) P P with p 6 q dovalid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseif valid thenE E {(p, q)}construct sorted node list L of CH(P ) from Ereturn L18 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
A First AlgorithmFirstConvexHull(P )Check all possibleE edges (p, q)foreach (p, q) P P with p 6 q dovalid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseif valid thenE E {(p, q)}construct sorted node list L of CH(P ) from Ereturn L18 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
A First AlgorithmFirstConvexHull(P )Check all possibleE edges (p, q)foreach (p, q) P P with p 6 q dovalid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseTest in O(1) time withif valid thenE E {(p, q)}xrxpxqyrypyq111 0construct sorted node list L of CH(P ) from Ereturn L18 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Running Time AnalysisFirstConvexHull(P )E foreach (p, q) P P with p 6 q dovalid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseif valid thenE E {(p, q)}construct sorted node list L of CH(P ) from Ereturn L19 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
FirstConvexHull(P )E foreach (p, q) P P with p 6 q dovalid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseΘ(1)Running Time Analysisif valid thenE E {(p, q)}construct sorted node list L of CH(P ) from Ereturn L19 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
FirstConvexHull(P )E foreach (p, q) P P with p 6 q dovalid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseΘ(1)Θ(n)Running Time Analysisif valid thenE E {(p, q)}construct sorted node list L of CH(P ) from Ereturn L19 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Running Time AnalysisΘ(1)Θ(n)FirstConvexHull(P )E foreach (p, q) P P with p 6 q do(n2 n)·valid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseif valid thenE E {(p, q)}construct sorted node list L of CH(P ) from Ereturn L19 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Running Time AnalysisΘ(1)Θ(n)Θ(n3 )FirstConvexHull(P )E foreach (p, q) P P with p 6 q do(n2 n)·valid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseif valid thenE E {(p, q)}construct sorted node list L of CH(P ) from Ereturn L19 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Running Time AnalysisΘ(1)Θ(n)Θ(n3 )FirstConvexHull(P )E foreach (p, q) P P with p 6 q do(n2 n)·valid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseif valid thenE E {(p, q)}construct sorted node list L of CH(P ) from Ereturn LQuestion: How do we implement this?19 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Running Time AnalysisΘ(1)Θ(n)Θ(n3 )FirstConvexHull(P )E foreach (p, q) P P with p 6 q do(n2 n)·valid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseconstruct sorted node list L of CH(P ) from Ereturn L19 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureO(n2 )if valid thenE E {(p, q)}Introduction & Convex Hulls
Running Time AnalysisΘ(1)Θ(n)Θ(n3 )FirstConvexHull(P )E foreach (p, q) P P with p 6 q do(n2 n)·valid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid falseO(n2 )if valid thenE E {(p, q)}construct sorted node list L of CH(P ) from Ereturn LLemma: The convex hull of n points in the plane can becomputed in O(n3 ) time.19 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Running Time AnalysisO(n2 )Θ(1)Θ(n)Θ(n3 )FirstConvexHull(P )E foreach (p, q) P P with p 6 q do(n2 n)·valid trueforeach r P do if not (r strictly right of pq or r pq) thenvalid false?rettbeodif valid thenwenaCE E {(p, q)}construct sorted node list L of CH(P ) from Ereturn LLemma: The convex hull of n points in the plane can becomputed in O(n3 ) time.19 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Incremental ApproachIdea: For i 1, . . . , n compute CH(Pi ) where Pi {p1 , . . . , pi }Question: Which ordering of the points is useful?20 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Incremental ApproachIdea: For i 1, . . . , n compute CH(Pi ) where Pi {p1 , . . . , pi }Question: Which ordering of the points is useful?Answer: From left to right!20 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Incremental ApproachIdea: For i 1, . . . , n compute CH(Pi ) where Pi {p1 , . . . , pi }Question: Which ordering of the points is useful?Answer: From left to right!upper hullConsider the upper andlower hull separatelylower hull20 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Incremental ApproachIdea: For i 1, . . . , n compute CH(Pi ) where Pi {p1 , . . . , pi }Question: Which ordering of the points is useful?Answer: From left to right!upper hullConsider the upper andlower hull separatelyUpperConvexHull(P )lower hullhp1 , p2 , . . . , pn i sort P from left to rightL hp1 , p2 ifor i 3 to n doL.append(pi )while L 2 and the last 3 points in L do not form right turn doremove the second-to-last point in L?return L20 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Incremental ApproachIdea: For i 1, . . . , n compute CH(Pi ) where Pi {p1 , . . . , pi }Question: Which ordering of the points is useful?Answer: From left to right!upper hullConsider the upper andlower hull separatelyUpperConvexHull(P )lower hullhp1 , p2 , . . . , pn i sort P from left to rightL hp1 , p2 ifor i 3 to n doL.append(pi )while L 2 and the last 3 points in L do not form right turn doremove the second-to-last point in Lreturn L20 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Incremental ApproachIdea: For i 1, . . . , n compute CH(Pi ) where Pi {p1 , . . . , pi }Question: Which ordering of the points is useful?Answer: From left to right!upper hullConsider the upper andlower hull separatelyUpperConvexHull(P )lower hullhp1 , p2 , . . . , pn i sort P from left to rightL hp1 , p2 ifor i 3 to n dolower hull is handled similarly!L.append(pi )while L 2 and the last 3 points in L do not form right turn doremove the second-to-last point in Lreturn L20 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Running Time AnalysisUpperConvexHull(P )hp1 , p2 , . . . , pn i sort P from right to leftL hp1 , p2 ifor i 3 to n doL.append(pi )while L 2 and last 3 points in L do not form right turn doremove the second-to-last point from Lreturn L21 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Running Time AnalysisUpperConvexHull(P )hp1 , p2 , . . . , pn i sort P from right to leftO(n log n)L hp1 , p2 ifor i 3 to n doL.append(pi )while L 2 and last 3 points in L do not form right turn doremove the second-to-last point from Lreturn L21 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Running Time AnalysisUpperConvexHull(P )hp1 , p2 , . . . , pn i sort P from right to leftO(n log n)L hp1 , p2 ifor i 3 to n do(n 2)·L.append(pi )while L 2 and last 3 points in L do not form right turn doremove the second-to-last point from L?return L21 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Running Time AnalysisUpperConvexHull(P )hp1 , p2 , . . . , pn i sort P from right to leftO(n log n)L hp1 , p2 ifor i 3 to n do(n 2)·L.append(pi )while L 2 and last 3 points in L do not form right turn doremove the second-to-last point from L?return LAmortized Analysis Each point is inserted into L exactly once A point in L is removed at most once from L Running time of the for loop including the while loop is O(n)21 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
UpperConvexHull(P )hp1 , p2 , . . . , pn i sort P from right to leftO(n log n)L hp1 , p2 ifor i 3 to n do(n 2)·L.append(pi )while L 2 and last 3 points in L do not form right turn doremove the second-to-last point from L?O(n)Running Time Analysisreturn LAmortized Analysis Each point is inserted into L exactly once A point in L is removed at most once from L Running time of the for loop including the while loop is O(n)21 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
UpperConvexHull(P )hp1 , p2 , . . . , pn i sort P from right to leftO(n log n)L hp1 , p2 ifor i 3 to n do(n 2)·L.append(pi )while L 2 and last 3 points in L do not form right turn doremove the second-to-last point from L?O(n)Running Time Analysisreturn LAmortized Analysis Each point is inserted into L exactly once A point in L is removed at most once from L Running time of the for loop including the while loop is O(n)Theorem 1: The convex hull of n points in the plane can becomputed in O(n log n) time. Graham’s Scan.21 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Alternative Approach: Gift WrappingIdea: Begin with a point p1 of CH(P ), then find the next edge ofCH(P ) in clockwise order.22 Dr. Tamara Mchedlidze · Dr. Darren Strash · Computational Geometry LectureIntroduction & Convex Hulls
Alternative Approach: Gift WrappingIdea: Begin with a point p1 of CH(P ), then find the next edge ofCH(P ) in clockwise order.GiftWrapping(P )p1 (x1 , y1 ) rightmost point in P ; p0 (x1 , ); j 1while true dopj 1 arg max{ pj 1 , pj , q q P \ {pj 1 , pj }}if pj 1 p1 then break else j j 1return (p1
Rolf Klein: Algorithmische Geometrie Springer, 2nd Edition, 2005 M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry: Algorithms and Applications Both books are available in the library!Springer, 3rd Edition, 2008 David Mount: Computational Geometry Lecture Notes CMSC 754, U. Maryland, 2012
