• 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₀, p₁, and p₂. 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₃, p₄, ..., p_m〉. The intent is that after processing point p_i , stack S contains, from bottom to top, the vertices of CH({ p₀, p₁, ..., 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₀ 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₀.

More formally, Jarvis's march builds a sequence H = 〈p₀, p₁, ..., p_h-1〉 of the vertices of CH(Q). We start with p₀. As Figure 33.9 shows, the next convex hull vertex p₁ has the smallest polar angle with respect to p₀. (In case of ties, we choose the point farthest from p₀.) Similarly, p₂ has the smallest polar angle with respect to p₁, 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₀.