Convex Hull

1Smallest convex polygon containing the points

A set S of points in the plane is convex if every segment between two points of S stays inside S. The convex hull of a finite point set P is the smallest convex set that contains P — a convex polygon whose vertices are a subset of P. Every other point of P lies inside or on that polygon.

The hull is the object. Graham scan and divide-and-conquer are two ways to name its vertices. Interior points are not a second object; they are the points the algorithms discard.

Figure. Hull A-B-C-E-F in counterclockwise order. D is interior (terracotta) and is not a hull vertex. Positions are schematic, not a millimetre plot.

What belongs on the hull

1. ExtremeA vertex of the hull is a point of P that is a corner of the taut rubber-band.
2. InteriorA point strictly inside that polygon is not a hull vertex.
3. Collinear edgePoints in the middle of a hull edge may be kept or dropped by policy; they are not interior.

2Left turn from a cross product

Walking p \to q \to r, the signed area of triangle pqr is \mathrm{CCW}(p,q,r) = (q_x-p_x)(r_y-p_y) - (q_y-p_y)(r_x-p_x). Positive means a left turn at q (counterclockwise). Negative means a right turn. Zero means p,q,r are collinear.

Graham's stack pops while the last three points make a non-left turn, so the surviving chain is always a left-turning (convex) chain. The test is two multiplies and a subtract — not an angle in degrees.

Figure. Walk C(2,1) → D(1,1) → E(1,2). The cross product (−1)·1 − 0·(−1) is −1, a right turn at D, so Graham pops D. Positive CCW would have kept D.

Evaluate one turn

1. Two edgesVectors q-p and r-p (or r-q; the sign convention must stay consistent).
2. Cross(q_x-p_x)(r_y-p_y)-(q_y-p_y)(r_x-p_x).
3. SignPositive: keep q. Negative: q is a right-turn dent, pop it.

3Graham scan: polar sort, then a stack

Graham scan names the hull vertices in order. Choose the lowest point (leftmost on a tie) as the origin p_0. Sort the remaining points by polar angle around p_0 (break ties by distance). Then walk that order with a stack: push the next point; while the last three points on the stack are not a left turn, pop the middle one.

The sort is O(n \log n). The walk is O(n) because each point is pushed once and popped at most once. That is why Graham is O(n \log n), not O(n^2).

One Graham pass

1. OriginLowest y, then leftmost x.
2. SortPolar angle about the origin; CCW from the +x direction.
3. ScanPush; pop while CCW of the top three is \le 0.

Graham scan

def ccw(p, q, r):
    return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])

def graham(points):
    p0 = min(points, key=lambda p: (p[1], p[0]))
    rest = [p for p in points if p != p0]
    rest.sort(key=lambda p: (math.atan2(p[1] - p0[1], p[0] - p0[0]),
                             (p[0] - p0[0]) ** 2 + (p[1] - p0[1]) ** 2))
    stack = [p0]
    for p in rest:
        while len(stack) >= 2 and ccw(stack[-2], stack[-1], p) <= 0:
            stack.pop()
        stack.append(p)
    return stack

Coding lab. Graham scan on six points runs in the app, with checks on your output.

4Divide-and-conquer: hull halves, then tangents

The divide-and-conquer hull sorts the points by x-coordinate, recursively computes the hull of the left half and of the right half, and merges those two convex polygons. The merge finds the upper common tangent and the lower common tangent — the two bridges that touch each hull once — and drops every vertex that lies strictly between the two contact points on the inner sides.

Finding the two tangents is O(n) on already-convex chains (walk the chains until both bridges are supporting lines). So T(n) = 2T(n/2) + O(n) = O(n \log n) after the initial sort — the same class as Graham, a different split.

Figure. Upper tangent (0,2)-(3,2) and lower tangent (0,0)-(3,0). The terracotta mid points sit on the inner chains and are dropped. Schematic, not to scale.

One merge

1. SplitMedian x. Recurse on left and right.
2. TangentsUpper and lower common supporting lines of the two hulls.
3. Drop inner chainsVertices between the two contact points on each hull are interior to the merge.

5O(n log n), or O(n h) when h is tiny

Graham and D&C hull are both O(n \log n). Gift wrapping (Jarvis march) starts at an extreme point and, at each hull vertex, scans all remaining points to find the next one with the smallest polar step — O(n) work per hull edge, so O(nh) for h hull vertices.

Jarvis wins only when h is much smaller than \log n is large — a hull that is a triangle on a million interior points. In the worst case h = n (points already in convex position) and Jarvis is O(n^2). A comparison-based hull is \Omega(n \log n) because sorting reduces to it (lift numbers onto a convex curve).

No new point set — the three-row time table is the comparison.