The Convex Hull: Wrapping a Rubber Band Around Points

What "convex" actually means

A region is convex if, for any two points inside it, the entire straight segment between them also lies inside. A star or a crescent is not convex; a disk, a triangle, or any regular polygon is. The convex hull of a finite point set P is the intersection of all convex sets containing P — equivalently, the smallest-area (and smallest-perimeter) convex polygon enclosing every point.

Two facts make the hull tractable. First, its vertices are always a subset of the input points — the rubber band snaps to actual nails, never to empty space. Second, a point is a hull vertex if and only if there exists a line through it with all other points strictly on one side (a supporting line). Interior points and points lying on an edge between two vertices are not vertices. Every algorithm below is, at heart, a strategy for deciding which points earn that status.

The one primitive that powers everything: orientation

Almost every hull algorithm reduces to a single question about three points: does the path a → b → c turn left, turn right, or go straight? This is the orientation test, computed from the sign of a 2D cross product:

cross(a,b,c) = (b.x − a.x)·(c.y − a.y) − (b.y − a.y)·(c.x − a.x)

• > 0 → counter-clockwise (left turn)
• < 0 → clockwise (right turn)
• = 0 → the three points are collinear

Geometrically, this value is twice the signed area of triangle abc. It needs only subtractions and multiplications — no division, no square roots, no trigonometry — which is why robust hull code prefers it over comparing angles directly. Using exact integer or rational arithmetic, the orientation test can be made provably correct; with naive floating point it is the single biggest source of hull bugs.

Gift wrapping (the Jarvis march): the rubber band, literally

Gift wrapping mimics the physical intuition most directly. Start at a point guaranteed to be on the hull — the lowest point (smallest y, ties broken by smallest x). From the current hull point, pick the next point so that every other point lies to the right of the segment to it. That candidate is the most clockwise point; the wrapping line pivots to it and repeats until it returns to the start.

p = lowest_point(P)
hull = []
repeat:
  hull.append(p)
  q = any point ≠ p
  for r in P:
    if cross(p, q, r) < 0: q = r  # r is more clockwise
  p = q
until q == hull[0]
return hull

The loop invariant is that after each pivot, p is a confirmed hull vertex and the boundary has been traced in order. Each outer iteration emits one hull vertex and scans all n points, so the cost is O(nh), where h is the number of hull vertices. This is output-sensitive: if only a handful of points are on the hull it is nearly linear, but for points on a circle where h ≈ n it degrades to Θ(n²).

Graham scan: sort once, then a single sweep

Graham scan (R. L. Graham, 1972) breaks the quadratic ceiling. Pick the lowest point as the pivot, sort the remaining points by polar angle around it, then walk the sorted list maintaining a stack of the hull-so-far. At each new point, pop any stack top that would create a right turn (a clockwise, non-left turn), because such a vertex cannot be on the hull:

sort P by polar angle around pivot
stack = [P[0], P[1]]
for r in P[2..]:
  while len(stack) ≥ 2 and cross(stack[−2], stack[−1], r) ≤ 0:
    stack.pop()
  stack.push(r)

The invariant is that the stack always holds a convex, counter-clockwise chain. The sort costs Θ(n log n); the scan is Θ(n) amortized because each point is pushed once and popped at most once. So total time is Θ(n log n), dominated entirely by the sort. Andrew's monotone chain variant sorts lexicographically by (x, y) instead of by angle and builds the lower and upper hulls separately — same asymptotics, but it dodges angle computation and its numerical hazards, which is why it is the more common production choice.

Why Θ(n log n) is optimal — and how Chan beats it

You cannot do better than Ω(n log n) in the comparison model: sorting n real numbers reduces to a hull problem (map each number x to the point (x, x²) on a parabola; the hull returns them in sorted order). So any general hull algorithm inherits sorting's lower bound. Graham scan therefore is optimal for the worst case.

But that bound is about n, not output. Chan's algorithm (1996) is the clever synthesis: partition the points into groups of size m, run Graham scan on each, then run a gift-wrapping march across the groups, using binary search on each group's mini-hull to find the tangent in O(log m). By doubling a guess for m until it exceeds h, Chan achieves O(n log h) — optimal in both input and output size. When h is small (say h = 12 vertices around 10⁶ points), that is dramatically faster than n log n while never being worse.

Pitfalls: collinearity, degeneracy, and floating point

The convex hull is a minefield of edge cases that a textbook description glosses over:

• Collinear points. Three or more points on a hull edge force a decision: do you keep only the two endpoints, or all of them? Using < 0 vs ≤ 0 in the turn test changes the answer. Both are valid hulls; pick one convention and apply it consistently.
• Fewer than 3 points, or all points collinear. The hull degenerates to a segment or a single point. Real code must special-case n ≤ 2 and the all-collinear input, or it will loop forever or return garbage.
• Floating-point orientation. A cross product near zero can flip sign under rounding, producing a non-convex or self-intersecting result. Libraries like CGAL use exact geometric predicates (adaptive precision arithmetic) precisely to make the orientation test bulletproof.
• Duplicate points and the pivot tie-break. Angle sorting is undefined for coincident points; dedupe first and break angle ties by distance from the pivot.

A common misconception is that the convex hull is a clustering or smoothing tool — it is not. It captures only the extremal outline; a single outlier can balloon the hull, which is exactly why the hull is used for outlier-aware bounding but is a poor descriptor of a set's dense core.

Planar convex-hull algorithms compared. h is the number of vertices on the hull; n is the input size.

Algorithm	Time	Output-sensitive?	Core idea	When to prefer
Gift wrapping (Jarvis)	O(nh)	Yes	Wrap point-to-point along the boundary	Very small hull (h ≪ n)
Graham scan	Θ(n log n)	No	Sort by angle, scan with a stack	General 2D, simple to code
Andrew's monotone chain	Θ(n log n)	No	Sort by x, build lower + upper chains	Robust default, avoids angles
Chan's algorithm	O(n log h)	Yes	Combine Graham + gift wrapping	Optimal when h is unknown/small
QuickHull	O(n log n) avg, O(n²) worst	Partly	Divide by farthest-point splits	Practical, cache-friendly