Graham's Scan

Algorithm

Graham’s scan computes the convex hull in $\Theta(n \log n)$ time. It works by sorting points radially from a reference point and then building the hull incrementally using a stack.

Steps

1. Find anchor point $P_0$: Choose the point with the lowest $y$-coordinate (break ties by choosing the leftmost, i.e. smallest $x$). This point is guaranteed to be on the hull.

2. Sort remaining points: Sort the $n-1$ remaining points by polar angle around $P_0$, measured from the positive $x$-axis (horizontal line to the right). If two points have the same angle, keep only the one furthest from $P_0$ (the closer one is interior to the hull edge).

3. Build the hull: Use a stack.

   • Push $P_0$, then $P_1$, then $P_2$ (the first three points in sorted order).
   • For each remaining point $p$ in sorted order:
     • While the last two points on the stack (let’s call them top and next-to-top) and $p$ make a non-left turn (i.e. a right turn or collinear), pop the stack.
     • Push $p$.
   • After processing all points, the stack contains the hull vertices in CCW order.

Non-Left Turn Detection

Use the cross product. For points $A$ (next-to-top), $B$ (top), $C$ (new point):

$\text{cross}(B-A, C-A) \le 0 \implies \text{not a strict left turn}$

If the cross product is $\le 0$ (right turn or collinear), pop $B$.

Why No Trigonometry?

Sorting by polar angle does not require computing angles. Since all points (except $P_0$) are in the half-plane above or to the right of $P_0$, the polar angle $\theta$ satisfies $0 \le \theta < \pi$. Use the cross product as comparator:

For points $A$ and $B$ (both $\neq P_0$), $A$ comes before $B$ in polar angle order iff:

$(A - P_0) \times (B - P_0) > 0$

If the cross product is $0$, they are collinear; keep the further point.

Worked Example

Points: $(0,0)$, $(4,0)$, $(4,3)$, $(2,1)$, $(0,3)$, $(1,4)$.

Step 1: Anchor $P_0 = (0,0)$ (lowest $y$, leftmost for $y=0$).

Step 2: Sort by polar angle from $P_0$:

• $(4,0)$: angle $0^\circ$
• $(4,3)$: angle $\arctan(3/4) \approx 36.9^\circ$
• $(2,1)$: angle $\arctan(1/2) \approx 26.6^\circ$
• $(0,3)$: angle $90^\circ$
• $(1,4)$: angle $\arctan(4/1) \approx 76.0^\circ$

Sorted order (by cross product): $(4,0)$, $(2,1)$, $(4,3)$, $(1,4)$, $(0,3)$.

Step 3: Stack trace.

Iteration	Point	Stack before	Pop?	Stack after
Init	—	[]	—	[P0]
1	(4,0)	[P0]	—	[P0, (4,0)]
2	(2,1)	[P0, (4,0)]	—	[P0, (4,0), (2,1)]
3	(4,3)	[P0, (4,0), (2,1)]	Check (4,0)→(2,1)→(4,3)

Compute for iteration 3: $\overrightarrow{(4,0)-(2,1)} = (-2, -1)$? No — use the correct direction.

Let’s check turn from stack: $A = (4,0)$, $B = (2,1)$, $C = (4,3)$.

$\overrightarrow{AB} = (2-4, 1-0) = (-2, 1)$ $\overrightarrow{AC} = (4-4, 3-0) = (0, 3)$ $\text{cross} = (-2)(3) - (1)(0) = -6 < 0$

Right turn → pop B = (2,1). Stack becomes [P0, (4,0)].

Now check: $A = P_0 = (0,0)$, $B = (4,0)$, $C = (4,3)$.

$\overrightarrow{AB} = (4, 0), \overrightarrow{AC} = (4, 3)$ $\text{cross} = 4 \cdot 3 - 0 \cdot 4 = 12 > 0$

Left turn → push (4,3). Stack: [P0, (4,0), (4,3)].

| 4 | (1,4) | [P0, (4,0), (4,3)] | $A=(4,0), B=(4,3), C=(1,4)$: $\overrightarrow{AB}=(0,3), \overrightarrow{AC}=(-3,4)$ cross $= 0 \cdot 4 - 3 \cdot (-3) = 9 > 0$ → left turn, push.

| 5 | (0,3) | [P0, (4,0), (4,3), (1,4)] | $A=(4,3), B=(1,4), C=(0,3)$: $\overrightarrow{AB}=(-3,1), \overrightarrow{AC}=(-4,0)$ cross $= (-3)(0) - (1)(-4) = 4 > 0$ → left turn, push.

Hull: $(0,0) \to (4,0) \to (4,3) \to (1,4) \to (0,3) \to$ back to $(0,0)$.

Complexity Analysis

• Finding $P_0$: $\Theta(n)$
• Sorting by polar angle: $\Theta(n \log n)$ (dominates)
• Stack operations: each point pushed at most once, popped at most once → $\Theta(n)$

Total: $\Theta(n \log n)$, dominated by sorting.

Handling Collinear Points

If multiple points are collinear on a hull edge, only the furthest points are kept (the intermediate points are not vertices of the convex polygon). The sorting step handles this by removing closer collinear points, and the stack’s non-strict-left-turn check ($\le 0$) removes intermediate collinear points found during processing.

Summary

Step	Operation	Time
1. Find anchor	Scan for min $y$	$\Theta(n)$
2. Sort by polar angle	Cross product comparator	$\Theta(n \log n)$
3. Build hull	Stack with turn check	$\Theta(n)$
Total	—	$\Theta(n \log n)$
No trig?	Yes, cross products only	—
Hull output	CCW vertex list on stack	—