The Convex Hull Problem

Definition

The convex hull of a set of points $P$ in the plane is the smallest convex polygon that contains all points of $P$. Equivalently:

• It is the intersection of all convex sets containing $P$.
• It is the shape a rubber band would take if stretched around all the points and then released.

Properties

1. All hull vertices are points of $P$ (extreme points).
2. Any interior point of $P$ is not on the hull.
3. The hull has at least 3 vertices (assuming at least 3 non-collinear points).
4. The hull has at most $n$ vertices (all points on the boundary, e.g. points on a circle).
5. The furthest-apart pair of points in $P$ are both on the hull.

Input and Output

Input: A set of $n > 2$ points $p_i = (x_i, y_i)$ where $1 \le i \le n$. At least 3 points are not collinear (so the hull has non-zero area).

Output: An ordered list of points forming the convex hull (usually in counter-clockwise order).

Two common output formats:

1. List of hull vertices in CCW order.
2. List of hull edges forming the boundary.

Lower Bound: $\Omega(n \log n)$

The convex hull problem requires $\Omega(n \log n)$ time in the comparison model.

Proof by reduction from sorting: Given $n$ distinct numbers $a_1, a_2, \ldots, a_n$ to sort, map them to points on a parabola: $p_i = (a_i, a_i^2)$. All these points lie on the convex parabola $y = x^2$, so they are all on the convex hull. Computing the convex hull of these $n$ points and then reading the $x$-coordinates in hull order (either left to right or right to left depending on output order) yields the sorted sequence.

Since sorting takes $\Omega(n \log n)$ comparisons, convex hull must also take $\Omega(n \log n)$.

Output Sensitivity

The number of hull vertices is denoted by $h$ (where $3 \le h \le n$). Algorithms that run in time proportional to $h$ are called output-sensitive.

Algorithm	Time	Output-sensitive?
Graham’s Scan	$\Theta(n \log n)$	No
Jarvis’s March	$\Theta(nh)$	Yes
Prune and Search	$O(n \log h)$	Yes (asymptotically optimal)

If $h$ is small (e.g. $h = O(1)$ or $h = O(\log n)$), Jarvis march outperforms Graham scan. If $h = \Theta(n)$, Graham scan is better.

Applications

• Collision detection in physics simulations and games (hull provides a conservative bounding region).
• Shape analysis in computer vision.
• GIS and mapping: computing the outer boundary of a set of geographic points.
• Pattern recognition: feature extraction from point sets.
• Voronoi diagrams: the convex hull is the outer boundary of the unbounded Voronoi cells.

Five Algorithms for Convex Hull

Approach	Algorithm	Time
Rotational sweep	Graham’s Scan	$O(n \log n)$
Rotational sweep	Jarvis’s March	$O(nh)$
Incremental	Add points one by one	$O(n \log n)$
Divide and Conquer	Merge two hulls	$O(n \log n)$
Prune and Search	Chan’s algorithm style	$O(n \log h)$

The Tripos syllabus focuses on Graham’s Scan and Jarvis’s March.

Summary

Property	Detail
Definition	Smallest convex polygon containing all points
Hull vertices	$h$, where $3 \le h \le n$
Lower bound	$\Omega(n \log n)$ by reduction from sorting
Graham scan	$\Theta(n \log n)$, non-output-sensitive
Jarvis march	$\Theta(nh)$, output-sensitive
Key fact	Extreme points of any direction are on the hull
Cross product	Used for all turn-direction checks, no trig