The site's fourth Convex Hull entry, and unlike the other three, it
isn't a fourth way to solve the problem from scratch — it's a way of combining two of them.
Graham Scan is always O(n log n) but never
cheaper, even when the hull turns out to have only a handful of vertices.
Jarvis March can be much cheaper — O(nh),
where h is the hull size — but only if the caller already knows h is small;
guess wrong and it degrades to O(n²). Chan's Algorithm gets Jarvis March's output-sensitive
cost without needing to know h in advance: split the points into small groups, find each
group's mini-hull with Graham Scan, then gift-wrap Jarvis-March-style across just the mini-hulls
instead of every point. The group size is a guess — start small, and if the wrap doesn't close in time,
double the guess and start over. That guess-and-double trick is the actual namesake idea, not the
group-then-wrap structure alone.
Sixteen points, split into groups by plain array order — A–D, E–H, and so on, not by spatial proximity, since the algorithm never needs the groups to be spatially meaningful. Each group's color shows which group it's in; a group's mini-hull is computed first (via Graham Scan, already covered in full on its own page, so this page computes it directly rather than re-animating every comparison). Then the wrap begins: at each step, every group is asked for its own tangent point — the mini-hull vertex most extreme relative to the current hull vertex, the same "most extreme point" test Jarvis March uses, just restricted to one small group's mini-hull instead of every point — and the most extreme point among those group winners becomes the next hull vertex. The checkbox picks the group size: a guess of m = 4 (four groups of four) turns out too small for this point set's real 7-vertex hull and has to abort partway through; m = 8 (two groups of eight) succeeds on the first attempt.
The key fact the whole algorithm leans on: if a point is on the overall convex hull, it's
also on the convex hull of whichever group it happens to land in. A group is just a subset of
the same points, so anything that's extreme across the whole set is at least as extreme within any
subset containing it. That means throwing away every group's interior points and keeping only each
group's own mini-hull — cheap, since each group is small — never discards a point the real answer
needs. It also means the union of all the mini-hulls' vertices is a strict superset of the real hull,
so running Jarvis March's own wrap on just that union, instead of on all n points, must
land on the identical answer.
The per-step saving comes from not treating that union as one flat list. For a convex polygon's own
vertex set and a point outside it, there's exactly one vertex that's "most extreme" as seen from that
outside point — same idea as a taut string's contact point on a round object — and it can be found by
checking each group's mini-hull independently: the group's own most-extreme vertex relative to the
current hull point (its tangent point), found with the exact same cross-product
comparison Jarvis March's own page already walks through in full, just applied to a handful of points
instead of all n. This page finds each group's tangent with a plain linear scan over that
group's few mini-hull vertices, since the groups here are small enough that the constant-factor cost
doesn't matter for a demo; a production implementation would binary-search the mini-hull's vertices
instead (they're already in sorted angular order from Graham Scan), turning each group's tangent query
from O(m) into O(log m). Either way, comparing only the n/m
group winners against each other — rather than all n points — for each of the
h hull vertices is exactly where the savings over a flat Jarvis March wrap comes from.
The group size m is the one thing the algorithm can't know ahead of time, because it
wants m close to the true hull size h — too small and the wrap won't close
before running out of steps; too large and the per-group Graham Scan sorts start dominating. The fix
is to not guess once: start at a small m, cap the wrap at m steps, and if it
doesn't close in time, double m and start completely over. Because each doubling at least
doubles the group size, the total work across every failed attempt is a geometric series dominated by
the final, successful one — so even counting every wasted early guess, the total cost is
O(n log h), not O(n log h) per attempt times the number of attempts.
function cross(o, a, b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
function dist2(a, b) {
return (a.x - b.x) ** 2 + (a.y - b.y) ** 2;
}
function grahamHull(group) {
let pivot = group[0];
for (const p of group) if (p.y < pivot.y || (p.y === pivot.y && p.x < pivot.x)) pivot = p;
const rest = group.filter(p => p !== pivot).sort((a, b) => {
const aa = Math.atan2(a.y - pivot.y, a.x - pivot.x), ab = Math.atan2(b.y - pivot.y, b.x - pivot.x);
if (aa !== ab) return aa - ab;
return dist2(pivot, a) - dist2(pivot, b);
});
const stack = [pivot];
for (const p of rest) {
while (stack.length >= 2 && cross(stack[stack.length - 2], stack[stack.length - 1], p) <= 0) stack.pop();
stack.push(p);
}
return stack;
}
function tangent(from, hull) {
let best = hull.find(p => p !== from);
for (const p of hull) {
if (p === from || p === best) continue;
const c = cross(from, best, p);
if (c < 0 || (c === 0 && dist2(from, p) > dist2(from, best))) best = p;
}
return best;
}
// One attempt at group size m: gift-wrap over the mini-hulls, capped at m steps.
// Returns the closed hull, or null if it didn't close in time (m was too small).
function hullAttempt(pts, m, start) {
const groups = [];
for (let i = 0; i < pts.length; i += m) groups.push(pts.slice(i, i + m));
const miniHulls = groups.map(grahamHull);
const hull = [start];
let current = start;
for (let step = 0; step < m; step++) {
const candidates = miniHulls.map(h => tangent(current, h)).filter(Boolean);
let winner = candidates[0];
for (const p of candidates) {
if (p === winner) continue;
const c = cross(current, winner, p);
if (c < 0 || (c === 0 && dist2(current, p) > dist2(current, winner))) winner = p;
}
if (winner === start) return hull; // closed
hull.push(winner);
current = winner;
}
return null; // didn't close within m steps: guess too small
}
function convexHull(points) {
const pts = Array.from(new Set(points.map(p => JSON.stringify(p))), s => JSON.parse(s));
if (pts.length < 3) return pts; // fewer than 3 points: no polygon, see Pitfalls
let start = pts[0];
for (const p of pts) if (p.y < start.y || (p.y === start.y && p.x < start.x)) start = p;
for (let m = 2; ; m *= 2) {
const hull = hullAttempt(pts, Math.min(m, pts.length), start);
if (hull) return hull;
}
}The group-size guess isn't a tuning knob a caller sets once — it has to be discovered live,
or the complexity bound quietly disappears. Running hullAttempt at a single fixed
m still returns the right answer eventually if the step cap is removed (the merge logic
itself doesn't depend on m for correctness, only for cost — verified directly: uncapped,
this page's own m = 4 grouping still reaches the correct 7-vertex hull, just by taking 7
steps instead of stopping at a 4-step cap). But capping at a too-small m and not
restarting means either giving up with a wrong (incomplete) answer or silently falling back to
something slower — the doubling restart is what keeps both the answer correct and the cost bounded by
the eventual right guess, not by however many wrong guesses came first. Measured directly on this
page's own 16-point set (true hull size h = 7): the full convexHull driver
needs exactly three rounds — m = 2 fails, m = 4 fails, m = 8
succeeds — matching ⌈log₂ h⌉ rounds, not a number that grows with how badly the first
guess missed.
The groups don't need to be spatially clustered, and making them so isn't a real optimization. This page's own groups are plain array-order chunks — group 1 is whichever four points happen to come first, not "the four points in the bottom-left corner" — and the algorithm is provably correct regardless, because the key fact in Why It Works (a hull vertex is always a vertex of its own group's mini-hull) doesn't depend on which points end up grouped together, only on groups being small. Spatially clustering the groups first doesn't change the asymptotic cost either; it can only possibly help the hidden constant by shrinking each mini-hull's vertex count as candidates, which this page doesn't attempt to measure since it doesn't change what the demo is teaching.
Fewer than three points, or every point exactly collinear, isn't a polygon — the
same edge case Graham Scan and
Jarvis March both handle explicitly, inherited here for
the same reason: grahamHull is the same function verified on those two pages, called
directly rather than reimplemented, so its already-checked behavior on tiny or degenerate groups
carries over unchanged rather than needing its own separate check.
Time: O(n log h), where h is the true hull size — the
name-giving result. Each round at group size m costs O(n log m) for the
per-group Graham Scan sorts (n/m groups, each O(m log m)) plus
O(m · (n/m) log m) = O(n log m) for the capped wrap (at most m steps, each
comparing n/m group tangents found in O(log m) with binary search — this
page's own linear-scan simplification makes that O(m) instead, a demo-only constant-factor
difference, not an asymptotic one). Doubling m each round makes the total across every
round, failed guesses included, a geometric sum dominated by the final round at m around
h, giving O(n log h) overall rather than O(n log h) times the
number of rounds. That's never worse than Graham Scan's flat
O(n log n) (since h ≤ n always) and never worse than
Jarvis March's O(nh) either once
h is more than a small constant — the price is a fussier implementation with three moving
parts (a sort-and-sweep, a wrap, and a restart loop) instead of one. Space:
O(n) for the per-round groups and mini-hulls, plus O(h) for the returned hull
itself, the same output-only footprint as Jarvis March. A random 200-trial stress test against an
independent brute-force hull (varying point count and layout each trial) found zero mismatches, and a
direct check confirmed the guess-and-double loop above needs exactly ⌈log₂ h⌉ rounds on
this page's own point set, not a number tied to how small the first guess was. A fifth entry,
Monotone Chain, is one of the two building blocks this
page combines — its own flat coordinate sort is the same sweep-and-stack step run here on every small
group before the wrap. A sixth entry,
Divide-and-Conquer Convex Hull, merges through
tangent lines the same way this page's wrap step does when it compares two groups' tangent points —
but as the whole algorithm, applied recursively to every pair of sub-hulls rather than once per group
against a running total. See
Choosing a Convex Hull Algorithm for how
this fits alongside the other five.