Convex Hull · study.

The previous lesson gave us a single, deceptively far-reaching operation: the orientation of an ordered triple of points $A, B, C$ , read off the sign of the cross product

(B - A) \times (C - A) = (B_{x} - A_{x}) (C_{y} - A_{y}) - (B_{y} - A_{y}) (C_{x} - A_{x}) .

A positive value means $A \to B \to C$ turns counterclockwise (a left turn), a negative value means clockwise (a right turn), and zero means the three points are collinear. That one branch-free, multiplication-only test, with no divisions, no square roots, and no angles, is the entire geometric engine of this lesson. We now use it to solve the foundational problem of computational geometry: given $n$ points in the plane, find their convex hull.

The problem

The mental picture is exact and worth keeping: hammer a nail into the plane at each point, stretch a rubber band wide enough to enclose them all, and let go. The band snaps taut around the outermost points and traces the hull; the points it touches are the hull vertices, and everything else lands strictly inside.

The convex hull is the smallest convex polygon enclosing the points

A hull algorithm must report the vertices in boundary order (say counterclockwise). The naive approaches are slow: testing each ordered pair to see whether all other points lie on one side of the line through it identifies hull edges in $O (n^{3})$ ; gift-wrapping (Jarvis march) pivots from one hull vertex to the next in $O (nh)$ time, where $h$ is the number of hull vertices, good when the hull is tiny but $Θ (n^{2})$ when every point is a vertex. We can do better, and provably best, in $O (n log n)$ .

Gift-wrapping: from

p

pick

q

so every other point lies left of ray

p \to q

Andrew's monotone chain

The cleanest $O (n log n)$ algorithm sorts the points once and sweeps them with a stack, building the boundary in two passes.

The pop condition is pure orientation. Suppose the stack ends in $A, B$ and we are about to add $C$ . If $A \to B \to C$ is a left turn (cross product $> 0$ ), $B$ is a genuine corner of the hull-so-far and we keep it. If it is a right turn or collinear (cross product $\leq 0$ ), then $B$ is inside the corner that $C$ opens up (the rubber band would not touch $B$ ), so we pop $B$ and re-test with the new top. This is exactly the rejection drawn below.

Pop while the last three points don't turn counterclockwise

Here $A \to B \to C$ bends to the right, so the chain dips below the convex boundary at $B$ . The algorithm pops $B$ and the corrected edge runs straight from $A$ to $C$ , restoring the all-left-turns invariant.

Inside the left-to-right sweep this plays out as a stack that grows and occasionally collapses. Below, the stack holds $p_{1} p_{2} p_{3}$ when $p_{4}$ arrives; the turn at $p_{3}$ is a right turn, so $p_{3}$ pops, and now the turn at $p_{2}$ is still a right turn, so $p_{2}$ pops too, leaving the taut chain $p_{1} p_{4}$ .

One sweep step:

p_{4}

arrives and cascades two pops,

p_{3}

then

p_{2}

, leaving the lower chain taut

Algorithm:

\textsc{Monotone-Chain}(P)

— convex hull of points

P

O(n\log n)

1
sort $P$ ascending by $(x, y)$ , removing duplicates
2
$L \gets [\,]$
lower hull
3
for each point $p$ in $P$ (left to right) do
4
while $|L| \ge 2$ and $\text{cross}(L_{-2}, L_{-1}, p) \le 0$ do
5
pop $L$
6
push $p$ onto $L$
7
$U \gets [\,]$
upper hull
8
for each point $p$ in $P$ (right to left) do
9
while $|U| \ge 2$ and $\text{cross}(U_{-2}, U_{-1}, p) \le 0$ do
10
pop $U$
11
push $p$ onto $U$
12
drop the last element of $L$ and of $U$
shared endpoints
13
return $L$ concatenated with $U$
counterclockwise

Here $L_{- 1}, L_{- 2}$ denote the top two stack elements and $cross (A, B, C)$ is the orientation value above. The last point of each chain is the first point of the other (the global min and max under the sort order), so we drop one copy of each to avoid duplicating the two extreme vertices.

Complexity. The sort costs $Θ (n log n)$ . Each sweep is linear despite the inner while: a point is pushed once and popped at most once, so the total number of pop operations across a sweep is at most $n$ . The work after sorting is therefore $Θ (n)$ , and the sort dominates: $O (n log n)$ overall.

Monotone chain builds the lower chain (

x

increasing) then the upper chain back

Graham scan: the classic alternative

The original $O (n log n)$ hull algorithm, Graham's scan, has the same skeleton but a different ordering. Pick the point with the lowest $y$ -coordinate (ties broken by $x$ ) as a pivot $p_{0}$ ; it is certainly a hull vertex. Sort the remaining points by polar angle around $p_{0}$ , then scan them in that angular order, maintaining a stack and popping whenever the last three points fail to turn left, the identical orientation test. Because the points are visited in angular order, one pass suffices to trace the whole boundary, again in $O (n log n)$ .¹ Monotone chain is usually preferred in practice precisely because it avoids the polar-angle sort: comparing $(x, y)$ lexicographically uses only the coordinates, whereas sorting by angle requires either $atan2$ (floating point, slow, imprecise) or cross-product comparisons with careful handling of the pivot, which means more code and more numerical fragility for the same asymptotics.

Degeneracies

Real inputs are not in general position, and the hull is where edge cases bite.

Duplicate points must be removed first (the sort makes this a linear scan); a repeated point can otherwise wedge a zero-length edge into the chain and break the turn test.
Collinear points on a hull edge are a deliberate policy choice, and it lives entirely in the comparison operator. Using $\leq 0$ in the pop condition (as above) discards collinear points, keeping only true corners — the minimal vertex set. Using $< 0$ keeps collinear points on the boundary, so a flat edge with interior points reports all of them. Problems like Erect the Fence, which ask for every point lying on the fence, want the $< 0$ variant; most geometry that follows (diameter, area) wants the lean $\leq 0$ hull. Decide which one your caller needs and pick the inequality accordingly.

A lower bound: $Ω (n log n)$

The $O (n log n)$ running time is not an artifact of these particular algorithms. No comparison-based hull algorithm can beat it, by the same lower-bound argument that pins comparison sorting.

Lifting

x_{i} \mapsto (x_{i}, x_{i}^{2})

puts every point on a convex parabola, so the hull sorts the

x_{i}

So monotone chain and Graham scan are asymptotically optimal: the sort they pay for is, in a precise sense, the same sort the problem secretly requires.

What the hull is good for

The hull is rarely the final answer. It is a preprocessing step that collapses $n$ messy points down to an ordered convex polygon of $h \leq n$ vertices, after which many extremal questions become easy. The key technique is rotating calipers: walk two pointers around the hull in tandem, exploiting the fact that as one supporting line rotates, the farthest or nearest vertex advances monotonically.² This computes the polygon diameter (the farthest pair of points in the whole set, which must be two hull vertices) in $O (n)$ time after the hull, rather than the $Θ (n^{2})$ of checking all pairs.

Rotating calipers: two parallel supporting lines turn around the hull; the diameter is the widest antipodal pair

The same caliper sweep yields the smallest enclosing rectangle (its optimal orientation always has a side flush with a hull edge), the width of the point set, and the convex layers (peel the hull, recurse on the interior). Whenever a problem cares only about the outermost shape of a point cloud (collision bounds, fitting, nearest-feature queries), computing the hull first is the standard opening move.³

Takeaways

The convex hull is the smallest convex polygon enclosing a point set (the rubber band around the nails), and reporting it in boundary order is the foundational problem of planar computational geometry.
Andrew's monotone chain sorts by $(x, y)$ , then sweeps a lower and upper hull, popping any vertex where the last three points fail to turn counterclockwise (cross product $\leq 0$ ). It is $O (n log n)$ , dominated by the sort.
The pop condition is the orientation primitive from the previous lesson: keep left turns, reject right turns and (by policy) collinear points.
Graham scan achieves the same bound by sorting on polar angle; monotone chain avoids angle computation and is more numerically stable.
Degeneracies, namely duplicates and collinear hull-edge points, are handled by deduplicating and by choosing $< 0$ (keep collinear) versus $\leq 0$ (drop them).
Any hull algorithm is $Ω (n log n)$ by reduction from sorting (lift points onto a parabola), so these algorithms are optimal.
The hull is a preprocessing step: rotating calipers give the diameter, smallest enclosing rectangle, and width in $O (n)$ once the hull is built.

CLRS, Ch. 33 — Computational Geometry (§33.3): Graham's scan sorts by polar angle around the lowest point and maintains a stack of left turns, in $O (n log n)$ . ↩
Skiena, § — Convex Hull: the hull as the most basic geometric structure, with rotating calipers for farthest-pair and enclosing-shape queries. ↩
CLRS, Ch. 33 — Computational Geometry (§33.3): the convex hull as a preprocessing primitive reducing $n$ points to an ordered convex polygon. ↩

The problem

Andrew's monotone chain

Graham scan: the classic alternative

Degeneracies

A lower bound: Ω(nlogn)

What the hull is good for

Takeaways

Footnotes

A lower bound: $Ω (n log n)$