Chan's Algorithm

Purpose: Compute a 2D convex hull in output-sensitive $O(n\log h)$ time, where $h$ is the number of hull vertices — beating the $O(n\log n)$ of Graham scan when the hull is small.

The Idea: guess $h$, then combine

Chan’s algorithm marries two hull algorithms:

• Graham scan — $O(n\log n)$, good on small groups;
• Jarvis march (gift wrapping) — $O(nh)$, output-sensitive but slow per step.

The combination:

1. Guess a value $m$ for $h$.
2. Partition the $n$ points into $\lceil n/m\rceil$ groups of size $m$. Compute each group’s hull with Graham scan: $O\left(\frac{n}{m}\cdot m\log m\right)=O(n\log m)$.
3. Run a Jarvis march on the whole point set, but find each next hull vertex by binary searching the tangent from the current point to each small hull — $O(\log m)$ per group, so $O\left(\frac{n}{m}\log m\right)$ per step.
4. Stop after $m$ steps. If the hull closed, output it. If not, $m<h$: double $m$ and restart.

The doubling trick

Start at $m=2$ and square it each round: $m=2^{2^t}$. The total cost is dominated by the last round, where $m\ge h$:

${\sum }_{t}O\left(n\log 2^{2^t}\right)={\sum }_{t}O(n{2}^t)=O(n\cdot 2^{\lceil \log \log h\rceil })=O(n\log h).$

Squaring rather than doubling is what makes the geometric series collapse to $O(n\log h)$ rather than $O(n{\log }^{2}h)$.

Complexity

• Time: $O(n\log h)$ — optimal for output-sensitive hull computation
• Space: $O(n)$

Convex hull algorithms compared

Algorithm	Time	Notes
Jarvis march (gift wrapping)	$O(nh)$	output-sensitive but slow; fine when $h$ is tiny
Graham scan	$O(n\log n)$	sort by angle; classic
Andrew’s monotone chain	$O(n\log n)$	sort by $x$; write this — simpler, no angles, no precision headaches
QuickHull	$O(n\log n)$ avg, $O(n^2)$ worst	divide and conquer
Kirkpatrick-Seidel	$O(n\log h)$	the “ultimate” hull; complicated
Chan	$O(n\log h)$	much simpler than Kirkpatrick-Seidel
Melkman	$O(n)$	for a simple polyline input only

In a contest

Andrew’s monotone chain, every time. $O(n\log n)$ with $n\le 10^6$ is nothing, and the code is 20 lines with only integer arithmetic if the coordinates are integers. Chan’s algorithm is worth knowing for the technique, not the constant.

The transferable technique

“Guess the output size, run a doubling search, and pay only for the last guess” is a general pattern. It also gives:

• output-sensitive 3D hulls,
• $k$-th smallest / selection with unknown $k$-dependent bounds,
• any algorithm whose cost is $f(n,m)$ with $m$ unknown but verifiable.

Variants / Use Cases

• Convex Hull — the topic page
• 3D convex hull — Chan’s technique extends to $O(n\log h)$ in three dimensions
• Rotating calipers — what you do after building the hull (diameter, width, closest pair of hulls)
• Kirkpatrick-Seidel — the other optimal output-sensitive hull