The Rubber Band Problem
Imagine pushing pins into a board at random positions, then stretching a rubber band around all of them. The shape it forms is the convex hull — the tightest convex boundary enclosing every point. This intuitive operation is one of the most fundamental problems in computational geometry, appearing as a subroutine in collision detection, image processing, and geographic analysis.
Gift-Wrapping: The Intuitive Algorithm
The Jarvis march (1973) mimics wrapping a gift: start at the leftmost point, then repeatedly pivot to the point making the smallest angle. Each step finds one hull vertex by scanning all points, taking O(n) time per vertex and O(nh) total. When h is small (few hull vertices), this is efficient; when all points are on the hull, it degrades to O(n²).
Graham Scan: Sort and Stack
Ronald Graham's 1972 algorithm takes a different approach: sort all points by polar angle, then process them in order using a stack. Each point either extends the hull (left turn) or triggers backtracking (right turn pops the stack). The stack ensures each point is processed at most twice, giving O(n log n) total — dominated by the initial sort.
Output-Sensitive Optimality
Neither gift-wrapping nor Graham scan is optimal in all cases. Timothy Chan's 1996 algorithm achieves O(n log h) — optimal for every input. It partitions points into groups, runs Graham scan on each group, then gift-wraps the group hulls. This elegant combination exploits the best properties of both predecessors.