The Convex Hull category's eleventh entry, and a fifth "different question" alongside
Rotating Calipers,
Convex Hull Trick,
Melkman's Algorithm, and the
Akl–Toussaint Heuristic — but a different kind
of different from all four: it doesn't skip computing a hull, or compute one from an unusual input, or
avoid computing one at all. It computes every hull. Take the convex hull of the whole point
set — the outer layer, sometimes called the outer onion ring — set
those points aside, then take the convex hull of whatever's left, and repeat until nothing remains.
Depth statistics call the result convex hull peeling: a point's layer number is a
measure of how "central" it is, popularized as a way to define a multivariate median (the innermost
layer) without ever picking a coordinate axis to sort by. Robust-statistics literature traces the idea
to Barnett (1976); the reference implementation below is the straightforward one — call a real hull
algorithm, remove its output, repeat — not the specialized O(n log n)-total algorithm
Chazelle gave in 1985 for the whole peel at once (see Complexity for what
that specialization actually buys).
22 points arranged in four rough rings. Press Step or Run: each round finds the convex hull of whatever points are still unassigned, colors that hull's vertices for the current layer, and removes them before the next round starts. This demo set was built with no exactly-collinear boundary points on purpose, so every round's hull is unambiguous — see Pitfalls for what happens on a set that isn't this clean.
Termination and well-definedness both fall out of the same fact this whole category leans on
constantly: for three or more points that aren't all collinear, a convex hull always has at least
three vertices, so every round strictly shrinks the remaining set by at least three points (fewer only
in the fully-degenerate collinear case, which still shrinks by at least the two extreme points). A
strictly shrinking, non-negative integer sequence can't run forever, so the peel always finishes in at
most n rounds, usually many fewer. What's left after the last round with three or more
points is either empty, one point, or two — never enough to form a polygon, but still a genuine final
layer (a single point, or a segment) and not a case to silently drop. See
Pitfalls for what happens when an implementation drops it anyway.
Nesting — layer k+1 never pokes outside layer k's boundary — follows
directly from what a convex hull already guarantees: every point not chosen for layer k
was, by definition, inside or on layer k's hull (that's what "convex hull of the whole
remaining set" means), and removing points from a set can only shrink its hull, never grow it. So
layer k+1's hull is contained in layer k's hull by construction, every
round, with no separate proof needed beyond the ordinary convex hull guarantee each round already
gives for free.
The one place this needs its own decision, not inherited from the six mechanism-comparison entries in Choosing a Convex Hull Algorithm, is collinear boundary points — and here it's sharper than the "vertex count" style choice those six make. A point sitting exactly on the segment between two hull corners is still genuinely on the current layer's boundary, at the current layer's depth, whether or not it gets named as a polygon vertex. Popping it the way this category's strict mode does elsewhere doesn't just drop it from a vertex list here — it leaves it in the remaining set, so the next round reports it one layer deeper than it actually sits. That's not a stylistic choice the way it is for a single hull (the region is identical either way); it's a wrong answer to the question this page's whole point is answering. See Pitfalls for the concrete misassignment.
function cross(o, a, b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
// loose/inclusive mode: cross(...) < 0 pops, so an exactly-collinear boundary
// point survives on the hull instead of being treated as interior — see Why it
// works for why that's not optional here the way it is for a single hull.
function hullLoose(points) {
const pts = points.slice().sort((a, b) => a.x !== b.x ? a.x - b.x : a.y - b.y);
if (pts.length < 3) return pts.slice();
function build(seq) {
const stack = [];
for (const p of seq) {
while (stack.length >= 2 && cross(stack[stack.length - 2], stack[stack.length - 1], p) < 0) {
stack.pop();
}
stack.push(p);
}
return stack;
}
const lower = build(pts);
const upper = build(pts.slice().reverse());
lower.pop(); upper.pop();
return lower.concat(upper);
}
function convexLayers(points) {
let remaining = points.slice();
const layers = [];
while (remaining.length >= 3) {
const hull = hullLoose(remaining);
const onHull = new Set(hull);
layers.push(hull);
remaining = remaining.filter(p => !onHull.has(p));
}
// 0, 1, or 2 points can be left — not a polygon, but still a real final
// layer (the "core"). See Pitfalls for what dropping this silently costs.
if (remaining.length > 0) layers.push(remaining);
return layers;
}Strict collinear popping doesn't just change a vertex count here — it reassigns a point to
the wrong layer, silently. Checked directly with a small hand-built set: a square
A(0,0), C(100,0), D(100,100), E(0,100) with a fifth point B(50,0) sitting
exactly on the bottom edge between A and C, plus two interior points
F(40,40) and G(60,55). The correct loose-mode peel reports two layers —
{A, B, C, D, E} (5 points, the outer ring, B included) then
{F, G} (the 2-point core) — matching the geometric fact that B sits on the
outer boundary. Swap in this category's usual strict popping (cross(...) <= 0 instead
of < 0) and nothing crashes, no point vanishes, but B gets silently
demoted: layer 1 becomes {A, C, D, E} (4 points, B popped as "not a real
corner"), and B survives into a bogus layer 2 alongside F and G
— reported one layer deeper than its true position, with no error and no warning, because from strict
mode's point of view B was correctly excluded from the polygon, exactly as it's supposed
to be for every other entry in this category. The bug isn't in the popping rule itself (it's the
right rule for a single hull) — it's in reusing it here without noticing that this page needs "on the
boundary" answered as "yes, this layer," not "no, not a vertex."
A loop that stops as soon as fewer than three points remain silently drops the innermost
core instead of reporting it as a final layer. The natural way to write the peeling loop is
while (remaining.length >= 3) { ...push a layer... } — correct for every round that
still forms a polygon, but if that's the entire function (no check after the loop for
whatever's left), the last one or two points never get pushed anywhere and simply disappear from the
output. Measured across 1,000 random trials (5 to 44 points each, uniform in a square): the peel ends
with exactly 0 points left over 448 times (the layers happened to divide the input exactly), but 1 or
2 points left over the other 552 times — a bug that manifests on 55.2% of realistic
random inputs, not a rare edge case. The fix is the reference implementation's own trailing
if (remaining.length > 0) layers.push(remaining) — a single-point or two-point "layer"
is a legitimate answer (the innermost point of an odd-sized peel, or a short segment for an even-sized
one), not a case to special-case away.
Per layer: the reference implementation calls Monotone
Chain's own O(m log m) hull on whatever m points remain that round — no
different from computing a single hull, since that's exactly what each round does. Total,
worst case: genuinely O(n²), not O(n log n) — measured, not
assumed. A deliberately adversarial input (n/3 concentric near-triangles, each just barely
inside the last, so every single round's hull has only 3 vertices) forces Θ(n) rounds,
each re-sorting nearly the entire still-shrinking remaining set from scratch. Instrumented directly
(summing the remaining-set size at the start of every round, the dominant cost each round pays): the
ratio of that total to n² holds essentially flat across six doublings of n
(0.183, 0.175, 0.171, 0.169, 0.168, 0.164 for n = 30 to 960) — a converging constant
ratio, the same signature Quickhull's own page uses to confirm
genuine quadratic growth rather than a curve that only looks steep at small n.
Typical case is much better, but still not the naive O(n log n) guess
a single-hull instinct might reach for. On points scattered uniformly at random, the number of layers
itself grows with n — measured (30 trials averaged per size): 6.53 layers at
n = 50, 10.67 at 100, 16.63 at 200, 26.40 at 400, 41.93 at 800, 66.40 at 1,600, 104.90 at
3,200. A log-log fit across those seven points gives a growth exponent of 0.665 —
close enough to n^(2/3) that it's worth flagging as consistent with published results on
random convex layers, but reported here as this page's own measurement, not an imported claim. That
many rounds, each re-sorting a shrinking-but-still-substantial remaining set, adds up to more than
linearithmic: total work (same remaining-size-per-round proxy as above) measured against
n across seven sizes from 30 to 1,920 fits a log-log exponent of
1.644 — distinctly worse than O(n log n)'s exponent of 1 (plus a log
factor), distinctly better than the worst case's 2. Space: O(n), same as
any single hull entry in this category — every point is stored in exactly one layer. Chazelle's 1985
algorithm brings the whole peel down to a guaranteed O(n log n) total by maintaining
hull structure incrementally across rounds instead of re-sorting from scratch each time — genuinely
different machinery, not implemented here, the same "naive-first, specialized-exists" gap
Jarvis March leaves for
Chan's Algorithm to close inside this same category.