In 1972, R. L. Graham proposed an efficient algorithm for planar convex hull. Historically, this is the first publication that showed convex hull computation in O(n log n) time in the worst case. In 1981, A. C. Yao proved that it is optimal in the worst-case sense. The problem with Graham’s algorithm is that it has no obvious extension to three dimensions. The reason is that the Graham’s scan depends on angular sorting, which has no direct counterpart in three dimensions.

Outline

First, select a base point p_o, normally this is the point with minimum y-coordinate. We select leftmost point in the set in case of the tie. Next, sort the points of Q lexicographically by polar angle, measured in radians. Interior points on the ray cannot be a convex hull points and remove these points during sort. Sort remaining points in counterclockwise order with respect to p_o. Push each point of set Q onto the stack once and the points that are not of CH(Q) are eventually popped from the stack.
 

Formal Algorithm
 

GRAHAM_SCAN(Q)

1. Let p_o be the point in given set Q with the minimum y-coordinate or leftmost point.
2. Let <p₁, p₂, …, p_m> be the remaining points in Q, sorted by polar angle in counterclockwise order with respect to p_o.
3. TOP [S] = 0
4. PUSH (p_o, S)
5. PUSH (p₁, S)
6. PUSH (p₂, S)
7. for i = 3 to m do
   1. while {angle between NEXT_TO_TOP[S], TOP[S], and p_i makes a nonleft turn} do
   2. PUSH (S, p_i)
8. return S

Running Time Computation
 

Line 1 requires O(n) time to find p_o (i.e., point with minimum y-coordinate). Line 2 requires O(n lg n) time, using merge or heap sort to sort polar angles. Lines 3, 4, 5, and 6 require constant time i.e., O(1). We use the aggregate method of amortized analysis to analyze while loop. As in analysis of MULTIPOP, we observe there is at most one ‘pop’ for each ‘push’ operation. In case of GRAHM’S SCAN, atleast three points (p_o, p₁ and p_m) are never popped from the stack. So infact, at most m - 2 pop operations are performed. Therefore, the mortised cost of each Iteration of while loop is O(n)/n = O(1). It implies that the overall worst-case for for-loop is O(n). The worst case running time of GRAHAM_SCAN is

T(n)  =  O(n) + O(n lg n) + O(1) + O(n) =  O(n lg n)         

 where n = |Q|

Correctness of Graham’s Scan

The correctness of Graham’s scan lies in two situations.
 

1. Part 1 deals with nonleft turns.
2. Part 2 deals with left turns.

Claim 1 Each point popped from the stack is not a vertex of CH(Q) and lies inside new CH(S).

FIGURE

Proof of Claim 1
 

Suppose that point p_j is popped from the stack because <p_kp_jp_i makes a nonleft turn. Since points are ordered in increasing polar angle w.r.t. p_o, there exists a triangle ∆ p_op_ip_k with p_j either in the interior of the triangle or on the line segment line(p_ip_k) (geometric property). Either case, point p_j cannot be a vertex of CH(Q). And this completes the proof of claim 1. □

 

Claim 2 The points on stack always form the vertices of a convex polygon.

 

Proof of Claim 2
 

The claim holds immediately after line 6, since points p_o, p₁, and p₂ form a convex polygon. Now examine how stack changes during the course of an algorithm. Stack changes in two ways. When:

1. Points are popped.
2. Points are pushed.

Case in which points are popped

Here we rely on geometric property: If a vertex is removed from a convex polygon, the resulting polygon is convex.

Case in which points are pushed

To analyze this case, we rely on the following geometric property.

 

FIGURES of Bounded region and unbounded region

Geometric Property

If we add point ps in the shaded regions to polygon P then the resulting polygon is convex.
Back to the case (when points are pushed).

 

Subclaim  If a point pi is pushed onto the stack, the resulting points form a convex polygon.

 

FIGURE

 

Proof of Subclaim:
 

By choice of p_o and p₁, p_i lies above p_op₁. By fact, a left turn occurs at p_j, p_i lies below p_jp_k. By fact, p_i occurs later in the sequence then p_j, the polar angle of p_op_i is greater than polar angle of p_op_j - p_i of lies left of line(p_op_j).
As a result p_i lies in the shaded region. Therefore after p_i has been pushed onto the stack, the points on stack form a convex polygon. This completes the proof. □
 

Conclusion

Since each point popped from the stack is not a vertex of CH(Q) ( by claim 1). And the points on stack always form the vertices of a convex polygon (by claim 2). Therefore Graham’s scan is correct.
 

Applet

Graham's scan starts with 25 random points, and then computes their convex hull.

The algorithm works in three phases:

1. Find an extreme point. This point will be the pivot, is guaranteed to be on the hull, and is chosen to be the point with smallest y coordinate.
2. Sort the points in order of increasing angle about the pivot. We end up with a star-shaped polygon (one in which one special point, in this case the pivot, can "see" the whole polygon).
3. Build the hull, by marching around the star-shaped poly, adding edges when we make a left turn, and back-tracking when we make a right turn.

You need a browser that understands java to view this applet. Otherwise, you will only see this message.

Thanks Alejo Hausner for codes.