The Convex Hull category's tenth entry, and a fourth "different question" alongside Rotating Calipers, Convex Hull Trick, and Melkman's Algorithm — but the most different of the five: it's the only one of the eleven that doesn't compute a hull, a diameter, or a max-at-query-x at all. Published by Akl and Toussaint in 1978, it's a genuine preprocessing filter that runs before a real hull algorithm, not instead of one. Scan every point once for eight directional extremes, connect them into a small convex octagon, and throw away every point that lands strictly inside it — none of them could possibly be a hull vertex, because the octagon they're inside of is itself already contained in the true hull. What's left — the octagon's own corners, plus anything outside or exactly on its boundary — is usually a small fraction of the input, ready to hand to Graham Scan, Quickhull, or any of this category's other nine single-hull entries to actually compute the hull — every entry here except Convex Layers, which needs the interior points this filter throws away to compute its own inner layers.
22 points, scattered with no special arrangement. Press Step or
Run: the algorithm first scans for eight directional extremes — leftmost,
rightmost, bottommost, topmost, and the four diagonal extremes (smallest/largest x+y
and x−y) — then draws the convex shape connecting them, then tests every other point
against it one at a time. Points strictly inside get discarded (faded); everything else, including
the extremes themselves, survives. The checkbox switches to the weaker classical version that uses
only four extremes (leftmost, rightmost, bottommost, topmost) instead of eight, forming a
quadrilateral instead of an octagon — same safety guarantee, visibly less pruning.
The core fact is about supporting lines, not about hulls directly. For any direction — "smallest
x," "largest x+y," any of the eight this page measures — the line
perpendicular to that direction, drawn through whichever point(s) achieve the extreme value, touches
the entire point set only from one side. A line with the whole point set on one side of it is a
supporting line, and every point lying on a supporting line is, by the definition of convex
hull, a point of the hull itself. So each of the eight extremes this heuristic measures is
guaranteed to be a genuine point of the true convex hull — not necessarily a "corner" if several
points tie for the same extreme value (this page's own demo set has exactly that: one point is
simultaneously the bottommost point and the max-(x−y) point, so the octagon
below has only seven distinct corners, not eight — see the log once you run it), but always on the
hull's boundary.
That's enough to prove the whole heuristic safe, in one step: the true convex hull is a convex region, and the convex hull of any subset of a convex region's own boundary points can never stick out past that region. The octagon built from (up to) eight genuine hull points is therefore always entirely contained within the true hull, however those eight points happen to be arranged. Any point strictly inside that octagon is consequently also strictly inside the true hull — and a point strictly inside a convex hull is, again by definition, never one of its vertices. Discarding it loses nothing. The quadrilateral version of this same argument, using only four extremes instead of eight, is identically safe for the identical reason; it's just a smaller, looser-fitting region, so it proves "strictly inside" for fewer points. See Complexity for how much that gap actually costs in practice.
The one thing this proof does not give is any claim about points outside the octagon, or exactly on its boundary. Those points aren't provably excluded — but they aren't provably included either. That asymmetry is the whole reason this is a filter and not a tenth way to compute the hull: the survivors still need a real algorithm (Graham Scan, Quickhull, the same nine other single-hull entries named above — not Convex Layers) to decide which of them are actual hull vertices and which were just lucky enough to dodge the octagon.
function findExtremes(points) {
const byMin = (key) => points.reduce((best, p) => key(p) < key(best) ? p : best);
const byMax = (key) => points.reduce((best, p) => key(p) > key(best) ? p : best);
return {
minX: byMin(p => p.x), maxX: byMax(p => p.x),
minY: byMin(p => p.y), maxY: byMax(p => p.y),
minSum: byMin(p => p.x + p.y), maxSum: byMax(p => p.x + p.y), // smallest/largest x+y
minDiff: byMin(p => p.x - p.y), maxDiff: byMax(p => p.x - p.y), // smallest/largest x-y
};
}
// walked in actual boundary order — NOT insertion order. See Pitfalls for what
// scrambling this order does to the "strictly inside" test below.
function octagon(ex) {
const order = [ex.minX, ex.minSum, ex.minY, ex.maxDiff, ex.maxX, ex.maxSum, ex.maxY, ex.minDiff];
const dedup = [];
for (const p of order) if (!dedup.length || dedup[dedup.length - 1] !== p) dedup.push(p);
if (dedup.length > 1 && dedup[0] === dedup[dedup.length - 1]) dedup.pop();
return dedup; // 8 corners, or fewer if a point ties for more than one extreme
}
function cross(o, a, b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
function filterCandidates(points) {
const oct = octagon(findExtremes(points));
// the polygon's own winding direction — needed so "strictly inside" means the same
// thing regardless of which way the eight points happen to wind
let signedArea = 0;
for (let i = 0; i < oct.length; i++) {
const a = oct[i], b = oct[(i + 1) % oct.length];
signedArea += (b.x - a.x) * (b.y + a.y);
}
const sign = signedArea < 0 ? 1 : -1;
const kept = new Set(oct);
for (const p of points) {
if (kept.has(p)) continue;
let strictlyInside = true;
for (let i = 0; i < oct.length && strictlyInside; i++) {
const a = oct[i], b = oct[(i + 1) % oct.length];
if (sign * cross(a, b, p) <= 0) strictlyInside = false;
}
if (!strictlyInside) kept.add(p); // not provably excluded — hand it to a real hull algorithm
}
return [...kept];
}The discard test has to be strict — "on the boundary" must count as keep, not
discard. Checked directly, not just argued: place a third point exactly on the segment
between two adjacent octagon corners — minX = (0, 40), minSum = (30, 10),
and a test point C = (15, 25), precisely their midpoint, so
cross(minX, minSum, C) = 0 exactly. The correct rule (discard only when the point is
strictly on the interior side of every edge, > 0 for all) reports
C as not strictly inside and keeps it, exactly as it should — C sits on the
octagon's own boundary, and the safety proof above says nothing about boundary points. A one-symbol
change to the inclusive version (>= 0, treating "on the edge" as "inside") reports
C as strictly inside and silently discards it — a real point, sitting exactly where the
octagon itself sits, thrown away before a real hull algorithm ever gets to decide whether it belongs.
This is the same strict-vs-loose boundary question every from-scratch entry in this category already
has to answer for its own collinear points (see
the guide's own section on it)
— the one-character bug here just fails silently instead of changing a vertex count, because a
discarded point never gets the chance to show up in a final hull count at all.
The eight extremes have to be connected in actual boundary order, not the order they were
found in. Every extreme-finding pass naturally produces its eight results in a fixed,
arbitrary order — minX, maxX, minY, maxY, minSum, maxSum, minDiff, maxDiff, say, matching
whatever order the code happens to check them in. Connecting them in that order instead of
walking the actual boundary (minX → minSum → minY → maxDiff → maxX → maxSum → maxY → minDiff)
produces a self-intersecting, bowtie-shaped polygon instead of a convex octagon. A stress harness
built for this page ran that exact swap across 300 random trials (15,087 points total): the "inside
all eight edges" test never once returned true — zero points discarded, 0% pruning,
on every single trial. This isn't a wrong-answer bug like the boundary case above; the safety
guarantee technically still holds (nothing gets wrongly discarded, because nothing gets discarded at
all), but the entire point of the heuristic — cutting the input down before a real hull algorithm
runs — silently stops happening, with no error, no crash, and no visibly wrong output. The only
symptom is a demo that's supposed to prune roughly three-quarters of its own 22 points and instead
prunes none.
Time: O(n), genuinely linear and not comparison-based — one pass to
track eight running extremes, a second pass testing each remaining point against at most eight fixed
half-planes (O(1) per point, since the octagon's side count never grows with
n). That makes this the cheapest entry in the entire category by asymptotic class,
cheaper than any of the nine algorithms that actually answer "what is the hull" — but it doesn't
answer that question itself, only "which points definitely aren't the answer." Space:
O(1) beyond the input and the surviving-points output; no recursion, no stack, no sort.
Pruning strength is where the real story is, and it depends heavily on the input. On uniform
random points in a square, a verification script for this page measured the surviving count after
filtering at increasing n: 25 of 100 (25.0%), 65 of 1,000 (6.5%), 278 of 10,000 (2.8%),
685 of 100,000 (0.69%) — shrinking toward the published O(√n) expected bound as
n grows, even if the small-n constant runs a bit above √n
itself. Across 500 independently generated random trials (24,998 points total), 19,097 were
discarded — 76.4% of the input thrown away before any real hull algorithm even started, with zero
false discards confirmed against an independent brute-force hull oracle. But the heuristic is only as
good as how much of the input is genuinely interior: a point set arranged in a tight ring (almost
every point on or near the true hull already) was pruned down to 100.0% kept at n = 200
and 98.95% kept at n = 2,000 — the octagon still costs its full O(n) pass,
for almost no benefit, its honest worst case. On this page's own 22-point demo set, the octagon keeps
8 (7 distinct corners plus one genuine survivor) against the quadrilateral's 13 — a concrete look at
the gap Why it works only argued for in the abstract. See
Choosing a Convex Hull Algorithm for
where the other ten entries fit once this one has done its work.