Read Chapter 1 from text by BKOS The procedure SlowConvexHull P pp 3 4 is a brute force algorithm taking O n3 time The algorithm on p 6 called ConvexHull P is a modification of Graham s Scan algorithm which is presented its original form below Read the rest of the chapter Sections 1 2 and 1 3 Extreme Point Lemma A point is non extreme iff it is inside some closed triangle whose vertices are points of the set and is not itself a corner of that triangle Proof of this lemma and an algorithm taking O n4 time are left as exercises An edge with two extreme vertices is called an extreme edge Develop an O n3 algorithm to determine the extreme edges of S Convex hulls Graham s scan Concept A point within a triangle of S cannot be a vertex of the convex hull Previous algorithm determined if a point p was within a triangle of S by trying as many as all of the triangles for each point p Can we find out if p is within a triangle of S more efficiently Graham s scan does so This algorithm is from one of the first papers specifically concerned with finding an efficient geometric algorithm 1972 The essential idea if a point p is not a vertex of the convex hull then it is internal to some triangle Op1p2 where O is an internal point and p1 and p2 are hull vertices But if we are trying to find the hull vertices where do p1 and p2 come from We shall see The algorithm consists of preparation and scan Single shot algorithm there is only one H S for a given S Convex hulls Graham s scan Centroid The centroid of a finite set of points p1 p2 pN is their arithmetic mean p1 p2 pN N Computed for each coordinate separately p2 2 1 5 p2 2 1 c 1 0 5 p1 3 1 Lexicographic sort Sorting on multiple keys associated with objects to be sorted Compare objects to be sorted on first key and sort accordingly If first keys are equal sort on second key If second keys are equal farther faster fastest father Convex hulls Graham s scan Polar angles The polar angle of a point p is the angle from the x axis through the origin to the point ascending counterclockwise y p1 p2 2 0 1 x Convex hulls Graham s scan y p1 p2 2 1 0 x Comparing polar angles Given two points p1 and p2 in the plane which has the greater polar angle p2 forms a strictly small polar angle with the x axis than p1 iff triangle 0p2p1 has a positive signed area Area triangle 0p2p1 x0 y1 x2 y0 x1 y2 x2 y1 x0 y2 x1 y0 2 See earlier slides on left turn right turn classification Equivalently iff 0p2p1 is a left turn Note that this means polar angles can be compared without actually computing them the latter requires trig functions Convex hulls Graham s scan Preparation The preparation for Graham s scan is as follows 1 Find a point O internal to H S the centroid of S O N 2 Transform the coordinates of the points in S so that O is the origin O N 2 Sort the N points of S lexicographically on 1 polar angle and 2 distance from O O N log N 3 Arrange the sorted points in a doubly linked circular list O N O Convex hulls Graham s scan Basic idea of the scan Recall that if a point p is not a vertex of the convex hull then it is internal to some triangle Op1p2 The scan examines the points in sorted order polar angle distance from O eliminating those not in the convex hull Point p2 H S and is eliminated when angle p1p2p3 is found to be reflex Equivalently eliminate p2 from H S iff p1p2p3 is not a left turn p3 p2 O Point p2 is within triangle Op1p3 and is eliminated p1 Convex hulls Graham s scan Scan algorithm informal The scan begins at the rightmost smallest ordinate minimum y coordinate point call it START START is certainly a hull vertex minimum y coordinate Repeatedly examine consecutive triples of points p1p2p3 If p1p2p3 is a right turn eliminate p2 from H S and backtrack to p0p1p3 If p1p2p3 is a left turn advance to p2p3p4 What about p1p2p3 collinear Eliminate p2 H S p3 p2 p1 p4 p0 O Scan ends when it advances to start i e p4 START START will never be eliminated because START H S Backtracking will not go back beyond predecessor of START Convex hulls Graham s scan Advancing and backtracking Backtracking may occur more than once in succession eliminating a sequence of points Backtracking sure to stop at START No point can be eliminated more than once O Convex hulls Graham s scan Algorithm See Preparata p 108 1 Find an internal point O 2 Using O as the coordinate origin sort the N points of S lexicographically by polar angle and distance from O Arrange the points into a doubly linked circular list with pointers NEXT and PRED for each entry and with pointer START pointing to the starting point 3 Scan 1 begin 2 v START 3 w PRED v w saves point just before START 4 f FALSE f indicates scan has returned to START 5 while NEXT v START or f FALSE 6 if NEXT v w then 7 f TRUE 8 endif 9 if Left v NEXT v NEXT NEXT v then 10 v NEXT v advance 11 else 12 delete NEXT v eliminate list operation O 1 13 v PRED v backtrack 14 endif 15 endwhile 16 end Convex hulls Graham s scan Analysis Time O N log N see comments Storage O N for circular linked list of points Comments Preparation Dominated by O N log N time required for sort Scan Left test requires O 1 time After each test either advance or backtrack The scan will advance at most O N times and will backtrack at most O N times The entire scan requires O N time Convex hulls Graham s scan Lower and upper hulls We introduce the notions of upper and lower hulls which will be useful later here in the context of Graham s scan Rather than comparing polar angles x coordinate values will be compared Given set S of N points in the plane find the points with minimum and maximum x coordinates abscissa Call those points l and r and construct the line L through l and r L partitions the remaining points S into two subsets upper and lower each of which include l and r Upper subset r L l Lower subset The lower respectively upper subset will induce a polygonal chain monotone w r t the x axis called the lower upper hull The concatenation of the two chains is the convex hull H S Convex hulls Graham s scan Constructing the upper hull Sort the points of the upper subset of S on decreasing …