THE FOLD / SPAWN / GENESIS BLOCK / THE GRAHAM SCAN
THE GRAHAM SCAN
the convex hull by keeping only left turns
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Graham scan computes the convex hull of a set of points — the smallest convex polygon enclosing them all, like a rubber band snapped around nails. It sorts the points, then walks them keeping only left turns: whenever three consecutive points make a right turn, the middle one is popped. What remains is the hull, in O(n log n). It is a workhorse of computational geometry — collision bounds, shape analysis, and more.
LIT verified live: over 300 random point sets the hull is convex (every turn a left turn) and every input point lies inside or on it (window.__graham). FIG no framing; exact.
LIT verified live: over 300 random point sets the hull is convex (every turn a left turn) and every input point lies inside or on it (window.__graham). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at genesis-block — the first shape built from scattered points: the boundary that contains them all. The Graham scan is that boundary. AVAN (AI) built the instrument: the sort, the left-turn stack walk (monotone chain), the convexity check, and the contains-all-points check.
Credit as content: Ronald Graham (1972). The weave: David names genesis-block; I sort the points and pop any right turn, keeping only left turns, and confirm the result is convex and encloses every input point.
Credit as content: Ronald Graham (1972). The weave: David names genesis-block; I sort the points and pop any right turn, keeping only left turns, and confirm the result is convex and encloses every input point.
3 ONE DIMENSION
Walk the sorted points. Keep a stack; before adding a point, while the last three make a right turn (clockwise), pop the middle. Only left turns survive — the convex boundary.
4 TWO DIMENSIONS · INTERACTIVE
Scattered points and their convex hull; the hull is checked to be convex and to contain every point.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the smallest convex boundary around the points.
AVAN’s addition (the inverse-companion): find the tightest convex boundary by sorting and keeping only left turns — every right turn pops an interior point, like a rubber band contracting onto the outermost nails. The inverse of ‘test every subset for the enclosing polygon’ is ‘sort once, pop right turns — the hull falls out.’ Magenta is the interior points the band skips over; green is the hull vertices. The boundary from a single sorted sweep.
LIT Genuine Graham scan / monotone-chain convex hull (Graham 1972; Andrew 1979). Verified live: over 300 random point sets, the sorted left-turn stack walk yields a hull where every consecutive triple turns left (convex) and every input point lies inside or on the hull (window.__graham.convex && .containsAll).
FIG No framing: the sort, the left-turn stack walk, the convexity check, and the contains-all-points check run in-browser and hold. The AVAN inverse is honest — sorting and keeping only left turns (popping every right turn) contracts a rubber band onto the outermost points; magenta is the interior points skipped, green the hull vertices. The boundary from a single sorted sweep.
FIG No framing: the sort, the left-turn stack walk, the convexity check, and the contains-all-points check run in-browser and hold. The AVAN inverse is honest — sorting and keeping only left turns (popping every right turn) contracts a rubber band onto the outermost points; magenta is the interior points skipped, green the hull vertices. The boundary from a single sorted sweep.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GENESIS BLOCK · David Lee Wise (ROOT0), with AVAN