Convex Hulls in the Plane

The Rubber-Band Idea

Imagine pushing rigid pins into a board at the locations of a set of 2D points. If you stretch a rubber band around all the pins and let it snap tight, it settles around the outermost pins. The minimal polygon traced by the taut band is the convex hull.

Mathematically, a shape is convex if it has no "dents" or inward folds: for any two points chosen inside the shape, the entire straight line segment connecting them lies completely inside. Simple shapes like triangles, circles, and rectangles are convex, whereas a crescent or a star with inward notches is non-convex. The convex hull fills in all such dents to form the smallest convex enclosure around the entire point set.

Reading the visual process from left to right:

• Panel 1: The input point set represented as rigid vertical pins.
• Panel 2: A loose elastic loop placed around all pins contracts uniformly under tension.
• Panel 3: The fully tightened band forms a convex polygon. The outer dark pins support the band and become hull vertices, while the interior gray pins remain enclosed and do not alter the boundary shape.

The green dashed line in the final panel demonstrates the fundamental mathematical property of convexity: joining any two interior points produces a segment that remains entirely within the boundary. If a new point is introduced outside the blue polygon, the hull stretches to incorporate it; if an interior point moves without crossing the perimeter, the hull remains unchanged. This distinction between boundary-defining vertices and interior points is the core insight leveraged by all convex hull algorithms.

Why Do Hulls Matter?

A hull is a compact summary of a point cloud. It throws away points that cannot affect the outer boundary while preserving an enclosure of all of them. That is useful whenever a system needs a quick outer limit, a broad-phase collision check, or a small set of extreme locations.

• Mapping and GIS: enclose a set of surveyed locations before doing more detailed region analysis.
• Robotics: approximate the footprint of a group of obstacles, then use the enclosure for a conservative first collision check.
• Computer graphics: compute a simple bounding shape for collision detection before testing detailed geometry.
• Manufacturing: summarize the outer extent of measured part points when planning storage, cutting, or inspection.

The Convex Hull Problem

Formally, for a finite set of points $S$, the convex hull is the smallest convex set containing every point in $S$. In the plane, when the points are not all on one line, its boundary is a polygon whose corners are selected from the input points.

The output is usually an ordered list of hull vertices—clockwise or counterclockwise—with the first vertex repeated only if an application specifically wants a closed ring. If there are no points, one point, or only collinear points, the output needs a clearly defined convention; we will return to these cases below.

This is the first full algorithmic problem in this series. It builds on the orientation test from the opening article: given three points, orientation tells whether they turn left, right, or lie on one line. The hull algorithms use that tiny decision repeatedly to decide which candidate points belong on the boundary.

A deliberately simple approach checks each pair of points $(p,q)$ as a possible hull edge. Keep the segment only if all other points lie on one side of its line. There are $O(n^2)$ pairs and up to $n$ checks per pair, so this takes $O(n^3)$ time. It is easy to reason about, but becomes slow quickly; the algorithms below avoid repeating so many checks.

Build a Hull by Hand

Before learning the formal algorithms, try this small point set: $A=(0,0)$, $B=(1,2)$, $C=(2,1)$, $D=(3,3)$, $E=(4,0)$, and $F=(2,-1)$. Looking at the points, the outer boundary is $F \to A \to B \to D \to E \to F$. Point $C$ is inside, so it cannot be a hull corner.

Notice that checking only which points are farthest from the centre would not be enough: hull corners depend on their order around the boundary. The orientation test helps determine whether a proposed next corner bends outward or cuts back into the shape.

Graham Scan

Graham scan gives us a systematic way to walk around the boundary. First choose a point that is guaranteed to be on the hull, often the one with the smallest $y$ coordinate. Sort all other points by their angle around that pivot. Then visit them in that order while keeping only the corners that make a counterclockwise (left) turn.

The working list is called a stack: the newest candidate goes on top, and a point can be removed from the top if it would create an inward bend. For each new point $p$, inspect the last two kept points $a,b$. If $a,b,p$ do not make the required left turn, remove $b$ and check again. Once the turn is valid, add $p$. In the usual strict-vertex version, collinear middle points are removed too.

Why is this efficient? Sorting takes $O(n\log n)$. During the scan, each point is pushed once and popped at most once, so all stack operations together take $O(n)$. The sort dominates, giving $O(n\log n)$ time. The Graham Scan spotlight contains a full implementation and a step-by-step trace.

Andrew's Monotone Chain

Andrew's monotone chain uses the same left-turn idea but gives the points an easier order: sort them from left to right by $(x,y)$. Make one pass to build the lower boundary, then a reverse pass to build the upper boundary. Join the two chains at their endpoints and you have the polygon.

For each pass, append the next point to a stack. While the last three points fail the chosen turn rule, pop the middle one. The left-to-right ordering ensures the lower and upper passes cannot zigzag arbitrarily across the point set. This avoids computing polar angles and often makes the method a convenient default for implementation.

On the six-point example above, sorting by $x$ gives a clear progression across the cloud. The lower pass rejects points that bend upward into the interior; the upper pass rejects points that bend downward into the interior. Each pass uses the same orientation calculation and stack rule.

The Andrew's Monotone Chain spotlight walks through the implementation and its lower/upper stacks in detail.

Collinear Points and Edge Cases

Some inputs have no single obvious polygonal answer. Three consecutive points can lie on one straight edge, many input points can be identical, or every point can lie on one line. The algorithm and the application must agree about what the output represents.

When three consecutive points are exactly collinear (orientation() == 0), two common policies are:

• Strict policy (pop on <= 0): a collinear middle point is treated as redundant and removed — the hull's boundary contains the fewest points needed to describe its shape.
• Inclusive policy (pop only on < 0): a collinear middle point is kept on the hull boundary — useful when the hull's vertex set (not just its shape) matters downstream, e.g. for reporting every point that lies on the convex boundary.

The strict policy is usually best when you need only the polygon's corners. The inclusive policy is useful when every point on the boundary matters, but it needs care when the input is fully collinear and when lower and upper chains are joined. Both spotlight implementations use the strict policy and show where the comparison changes.

Also define what to return for empty input, a single unique point, two unique points, duplicate coordinates, and an all-collinear set. For example, an API might return the sorted unique points for the all-collinear case under an inclusive policy, but only the two endpoints under a strict policy. These are interface choices, not details to leave implicit.

Why Sorting Appears

Both Graham scan and monotone chain sort before scanning, which costs $O(n\log n)$. That is not just a convenient design: in the comparison model, no general convex-hull algorithm can be asymptotically faster in the worst case.

The reason is a reduction from sorting. Take distinct numbers $x_1,\ldots,x_n$ and turn them into points $(x_i,x_i^2)$ on the curve $y=x^2$. Each point is on the lower convex boundary of this set, and walking along that boundary reveals the numbers in sorted $x$ order. So a hull algorithm also gives us a sorting algorithm. If the hull could always be found in less than $\Omega(n\log n)$ comparisons, sorting could too, contradicting the comparison-sorting lower bound.

In practical terms, $O(n\log n)$ is the expected optimal scale for a general planar hull when points are unordered and comparisons are the primitive operation. This is a worst-case statement; it does not rule out faster methods when the data has special structure or the hull has very few corners.

Output-Sensitive Alternatives

The $\Omega(n \log n)$ bound is about worst-case input; it says nothing about hulls with very few vertices $h \ll n$. Two output-sensitive algorithms exploit that:

• Jarvis march (gift wrapping) — starting from the lowest point, repeatedly find the next hull vertex by choosing, among all remaining points, the one that makes every other point lie to one side. Runs in $O(nh)$: cheap when $h$ is small, worse than $O(n \log n)$ once $h$ approaches $n$.
• Chan's algorithm (Timothy Chan, 1996) — combines small brute-force hulls with a Jarvis-march-style merge to achieve $O(n \log h)$, matching the information-theoretic optimum for any fixed $h$. It achieves this by guessing $h$ (doubling the guess each round, up to $\log h$ rounds), never fully computing more than that guess in Jarvis-march work per round.

For example, imagine a point cloud with a million samples but only a few dozen extreme points. The number of input points is $n$; the number of output corners is $h$. An output-sensitive method can benefit when $h$ is much smaller than $n$, though implementation complexity, coordinate distributions, and library quality also matter. Asymptotic bounds guide a choice; benchmarks on representative data confirm it.

Here $n$ is the number of input points and $h$ is the number of hull vertices. A practical starting point is Andrew's monotone chain: it has the optimal general comparison bound, avoids angle calculations, and is straightforward to test. Specialized methods are worthwhile when the workload and benchmarks give a clear reason.

Case Studies and Exercises

These examples connect the algorithm to engineering decisions. In production, computing the correct hull is only one part of the work: coordinate systems, duplicates, numerical precision, and what the consumer means by “boundary” all affect the result.

Visual Intuition: Boundary, Stack, and Algorithm Choice

The rubber band is more than a metaphor. Every hull edge lies on a supporting line with all input points in one closed half-plane. A point strictly inside the hull can be removed without changing the answer. This is why later convex-polygon algorithms work on $h$ hull vertices rather than all $n$ input points.

For sorted points (0,0), (1,2), (2,1), the orientation is $1\cdot1-2\cdot2=-3$. The right turn pops (1,2) from the lower hull before (2,1) is pushed. Each point is pushed once and popped at most once per chain, so the scans remain linear despite the nested while loop.

Where This Is Used Next

Convex hulls recur throughout the series: Part 5's rotating calipers operate directly on a hull's vertex sequence, Part 10's linear programming touches half-plane duals of hull edges, and Part 19 revisits the whole problem in three dimensions, where "hull" becomes a much harder combinatorial object. The next part leaves hulls aside and tackles a different classic: finding the two closest points in a set, in $O(n \log n)$, via divide and conquer.