Jarvis's March (Gift Wrapping)

Algorithm

Jarvis’s march (also known as the gift wrapping algorithm) computes the convex hull in $\Theta(nh)$ time, where $h$ is the number of hull vertices. It is output-sensitive: fast when $h$ is small, slower than Graham’s scan when $h = \Theta(n)$.

Intuition

Wrap a string around the set of points. Starting at the leftmost point, pull the string taut and rotate it counter-clockwise; the first point the string hits is the next hull vertex. Repeat until returning to the start.

Steps

1. Start point: Find the leftmost point $p_0$ (break ties by lowest $y$). This is guaranteed to be on the hull.

2. Find the next hull vertex: Given the current hull vertex $p_i$ and the previous hull vertex $p_{i-1}$ (for $i=0$, imagine $p_{-1}$ is a point with same $x$ as $p_0$ but $y = p_0.y - 1$, i.e. directly below), find the point $p_{i+1}$ that makes the smallest counter-clockwise angle from the directed segment $p_{i-1} \to p_i$.

3. Repeat until $p_{i+1} = p_0$.

Finding the Next Point

For each candidate point $q$ in the set, compare $q$ against the current best candidate $p_{\text{next}}$ using the cross product:

Given current point $p_i$ and previous point $p_{i-1}$, to determine whether $q$ is better than the current best:

$\text{orient}(p_{i-1}, p_i, q) > 0 \quad \text{or} \quad (\text{orient} = 0 \text{ and } q \text{ is further})$

If the orientation is positive, $q$ makes a larger CCW angle than best, so $q$ is better. If orientation is zero (collinear), choose the further point (the nearer one is interior to the hull edge).

This requires no trigonometry: the cross product comparator works because all searches are within half-plane ranges where $\sin \theta$ is monotonic in $\theta$ (i.e. for angles between $-\pi/2$ and $\pi/2$).

Right Chain and Left Chain

An alternative formulation splits the hull into two monotone chains:

1. Right chain: From the leftmost point to the rightmost point (or topmost, depending on convention), always finding the point with the smallest polar angle.
2. Left chain: From the rightmost/topmost point back to the leftmost, finding the point with the largest polar angle.

This ensures the polar angle search always stays in the range $[-\pi/2, \pi/2)$ where cross product comparisons are valid monotonic replacements for angle.

Worked Example

Points: $(0,0)$, $(4,1)$, $(3,3)$, $(1,4)$, $(-1,3)$, $(-2,1)$, $(2,2)$.

Step 1: Leftmost point $= (-2,1)$ (this is $p_0$).

Step 2 (first edge): Starting from $p_0 = (-2,1)$, with a reference direction pointing straight down (so the first edge goes to the point with smallest CCW angle from downward). In practice, scan all points:

For each point $q$: compute direction from $p_0$ to $q$. The point with the smallest CCW angle from the imaginary downward direction is the one that is “most to the right” relative to $p_0$ looking downward.

This yields $p_1 = (-1,3)$ — the one that makes the smallest CCW turn from the downward reference.

Step 3: From $p_0 = (-2,1)$ and $p_1 = (-1,3)$, find the point $q$ that maximizes the angle $\angle p_0 p_1 q$ (i.e. makes the leftmost turn).

Scan all points, use $\text{orient}(p_0, p_1, q)$ to compare. The point with the largest CCW turn (or furthest if collinear) is chosen.

This process continues, always choosing the leftmost turn from the current edge:

Step	From edge	Next hull point
1	(reference) → (-2,1)	(-1,3)
2	(-2,1) → (-1,3)	(1,4)
3	(-1,3) → (1,4)	(3,3)
4	(1,4) → (3,3)	(4,1)
5	(3,3) → (4,1)	(0,0)
6	(4,1) → (0,0)	(-2,1)

Hull vertices: $(-2,1) \to (-1,3) \to (1,4) \to (3,3) \to (4,1) \to (0,0) \to$ back. That’s $h = 6$ hull vertices from $n = 7$ points. Note that $(2,2)$ is interior and was never selected.

Complexity Analysis

• Each step scans all $n$ points: $O(n)$ per step.
• There are $h$ steps (one per hull vertex).
• Total: $\Theta(nh)$.

If $h$ is small, this beats Graham’s $\Theta(n \log n)$. If $h = \Theta(n)$, this is $\Theta(n^2)$, worse than Graham.

When to Use Each

Scenario	Preferred Algorithm
$h$ expected to be small ($h \ll n$)	Jarvis’s March $\Theta(nh)$
$h$ unknown or expected large	Graham’s Scan $\Theta(n \log n)$
Need asymptotically optimal	Prune and Search $O(n \log h)$

Summary

Property	Detail
Name	Jarvis’s March / Gift Wrapping
Time	$\Theta(nh)$
Output-sensitive	Yes
Space	$O(1)$ beyond input and output
Technique	Scan all points for next hull vertex
Comparison	Cross products, no trigonometry
Best when	$h \ll n$
Worst when	$h = \Theta(n)$ → $\Theta(n^2)$