Finding The Convex Hull
- The remainder of the procedure uses the stack S. Lines 3-5 initialize the stack to contain, from bottom to top, the first three points p_{0}, p_{1}, and p_{2}. Figure 33.7(a) shows the initial stack S. The for loop of lines 6-9 iterates once for each point in the subsequence 〈p_{3}, p_{4}, ..., p_{m}〉. The intent is that after processing point p_{i} , stack S contains, from bottom to top, the vertices of CH({ p_{0}, p_{1}, ..., p_{i}}) in counterclockwise order. The while loop of lines 7-8 removes points from the stack if they are found not to be vertices of the convex hull. When we traverse the convex hull counterclockwise, we should make a left turn at each vertex. Thus, each time the while loop finds a vertex at which we make a nonleft turn, the vertex is popped from the stack. (By checking for a nonleft turn, rather than just a right turn, this test precludes the possibility of a straight angle at a vertex of the resulting convex hull. We want no straight angles, since no vertex of a convex polygon may be a convex combination of other vertices of the polygon.) After we pop all vertices that have nonleft turns when heading toward point p_{i} , we push p_{i} onto the stack. Figures 33.7(b)-(k) show the state of the stack S after each iteration of the for loop. Finally, GRAHAM-SCAN returns the stack S in line 10. Figure 33.7(l) shows the corresponding convex hull.
Jarvis's march: Jarvis's march computes the convex hull of a set Q of points by a technique known as package wrapping (or gift wrapping). The algorithm runs in time O(nh), where h is the number of vertices of CH(Q). When h is o(lg n), Jarvis's march is asymptotically faster than Graham's scan. Intuitively, Jarvis's march simulates wrapping a taut piece of paper around the set Q. We start by taping the end of the paper to the lowest point in the set, that is, to the same point p_{0} with which we start Graham's scan. This point is a vertex of the convex hull. We pull the paper to the right to make it taut, and then we pull it higher until it touches a point. This point must also be a vertex of the convex hull. Keeping the paper taut, we continue in this way around the set of vertices until we come back to our original point p_{0}.
More formally, Jarvis's march builds a sequence H = 〈p_{0}, p_{1}, ..., p_{h-1}〉 of the vertices of CH(Q). We start with p_{0}. As Figure 33.9 shows, the next convex hull vertex p_{1} has the smallest polar angle with respect to p_{0}. (In case of ties, we choose the point farthest from p_{0}.) Similarly, p_{2} has the smallest polar angle with respect to p_{1}, and so on. When we reach the highest vertex, say p_{k} (breaking ties by choosing the farthest such vertex), we have constructed, as Figure 33.9 shows, the right chain of CH(Q). To construct the left chain, we start at p_{k} and choose p_{k 1} as the point with the smallest polar angle with respect to p_{k}, but from the negative x-axis. We continue on, forming the left chain by taking polar angles from the negative x-axis, until we come back to our original vertex p_{0}.