6.006 Intro to Algorithms Recitation 24 May 6, 2011Convex HullGiven a set of points Q, we may want to find the convex hull, which is a subset of points that formthe smallest convex polygon where every point in Q is either on the boundary of the polygon or inthe interior of the polygon. We can imagine fitting an elastic band around all of the points. Whenthe band tightens, the points that it rests on form the convex hull.There are several algorithms to solve the convex hull problem with varying runtimes.Graham’s ScanThe Graham’s scan algorithm begins by choosing a point that is definitely on the convex hull andthen iteratively adding points to the convex hull.1. Let H be the list of points on the convex hull, initialized to be empty2. Choose p0to be the point with the lowest y-coordinate. Add p0to H since p0is definitely inthe convex hull.3. Let (p1, p2, ..., pn) be the remaining points sorted by their polar angles relative to p0fromsmallest to largest. Iterating through the points in sorted order should sweep around p0incounterclockwise order4. For each point pi:(a) If adding pito our convex hull results in making a “left turn”, add pito H(b) If adding pito our convex hull results in making a “right turn”, remove elements fromH until adding pimakes a left turn, then add pito H.6.006 Intro to Algorithms Recitation 24 May 6, 2011Below is an example of left and right turns. At step 1, our convex hull H is (P, A, B). AddingC resulted in making a left turn at B if we’re going from A to C, so we add C to H, which is now(P, A, B, C). Adding D in step 2 resulted in making a right turn at C if we’re going from B to D.If we just added D now, we would not have a convex shape. To fix this, we remove elements fromH until adding D results in making a left turn. Simply removing C does the trick and we add Dafter C is removed from H. This results in the convex hull solution of H = (P, A, B, D).Note that there may be cases where we have to remove multiple points from H in order to fixthe convexity. Once we iterate through every point, H will form the convex hull.The bottleneck of the algorithm is sorting the points by polar angles. This operation requiresO(n log n) time. Since every point is added to H exactly once and every point is removed from Hat most once, iterating through the points and forming H after the sorting takes O(n) time. Thus,the whole algorithm takes O(n log n) time.6.006 Intro to Algorithms Recitation 24 May 6, 2011Jarvis’ marchThe Jarvis’ march algorithm conceptually is very similar to Graham’s scan. Again, we sort thepoints by their y-coordinates and choose p0in the same fashion as before. This time, we find thenext point in the convex hull by iterating through all n other points and discovering the next pointwith the smallest relative polar angle to the last point added to the convex hull. The difference hereis that each point we add is definitely on the convex hull, as opposed to Graham’s scan where eachpoint we add may need to be removed later. The tradeoff is that after each addition to the convexhull, we need to iterate through every other point to find the next point on the convex hull, whichtakes O(n) time. The algorithm terminates once we try to add p0to H again.The runtime of this algorithm is output-sensitive, meaning that the runtime depends on howmany points are on the convex hull solution. For each point on the convex hull, we need to spendO(n) time to iterate through all of the other points. Thus, if there are O(h) points on the convexhull, the runtime will be O(nh). If h = o(lg n), i.e. the convex hull is formed by a small portionof the total points, then Jarvis’ march outperforms Graham’s
View Full Document
Unlocking...