THE FOLD / CHEAT / THE SHORTCUT / THE QUICKHULL
THE QUICKHULL
wrap a hull by divide and conquer
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Quickhull finds the convex hull of a point set by divide and conquer — the quicksort of geometry. Take the two extreme points (leftmost, rightmost); the line between them splits the rest into two sides. On each side, find the point farthest from the line: it must be a hull vertex. That point makes a triangle, and any point inside it is discarded; the two outer sub-regions recurse. Points far from the current hull are found first, so clusters of interior points are culled quickly.
LIT verified live: over 1500 random point sets, quickhull’s hull (with collinear vertices canonicalized) equals an independent monotone-chain hull, and every point lies inside or on it (window.__quickhull). FIG no framing; exact orientation tests; collinear-vertex convention made explicit.
LIT verified live: over 1500 random point sets, quickhull’s hull (with collinear vertices canonicalized) equals an independent monotone-chain hull, and every point lies inside or on it (window.__quickhull). FIG no framing; exact orientation tests; collinear-vertex convention made explicit.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-shortcut — the divide-and-conquer shortcut to the hull; throw away the interior in bulk and recurse only on the frontier. Quickhull is that shortcut. AVAN (AI) built the instrument: the extreme-point split, the farthest-point recursion, the strict-hull canonicalization, and the match against a monotone-chain hull.
Credit as content: Quickhull (Eddy 1977; Bykat 1978; Barber–Dobkin–Huhdanpaa 1996). The weave: David names the-shortcut; I split by the extreme points, recurse toward the farthest point on each side discarding interiors, and confirm the resulting hull — canonicalized to strict vertices — matches a monotone-chain hull with every point enclosed.
Credit as content: Quickhull (Eddy 1977; Bykat 1978; Barber–Dobkin–Huhdanpaa 1996). The weave: David names the-shortcut; I split by the extreme points, recurse toward the farthest point on each side discarding interiors, and confirm the resulting hull — canonicalized to strict vertices — matches a monotone-chain hull with every point enclosed.
3 ONE DIMENSION
Leftmost–rightmost line splits the points. The farthest point on a side is a hull vertex; its triangle’s interior is dropped; the two outer wedges recurse. Divide and conquer, like quicksort.
4 TWO DIMENSIONS · INTERACTIVE
A point cloud with its quickhull; checked against a monotone-chain hull, all points enclosed.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a hull built by dividing and conquering.
AVAN’s addition (the inverse-companion): find the hull by recursively discarding interiors — split by extremes, take the farthest point as a vertex, drop everything inside its triangle, recurse on the outer wedges. The inverse of ‘test every point for hull membership’ is ‘cull the inside in bulk and recurse on the frontier.’ Magenta is the all-points membership test; green is the divide-and-conquer cull. The hull carved by throwing the middle away.
LIT Genuine Quickhull (Eddy 1977; Bykat 1978; Barber–Dobkin–Huhdanpaa 1996). Verified live: over 1500 random point sets, quickhull's hull — canonicalized to strict vertices (collinear ones removed) — has the same vertex set as an independent monotone-chain (Andrew) hull (window.__quickhull.matchesMonotone), and every input point lies inside or on it (allInside).
FIG Honestly scoped: quickhull and monotone-chain can differ on whether collinear boundary points count as hull vertices, so the sphere canonicalizes to strict vertices before comparing — the convention is made explicit, not hidden. The extreme-point split, farthest-point recursion, strict-hull canonicalization, and monotone cross-check run in-browser and agree. The AVAN inverse is honest — culling interiors in bulk and recursing on the frontier genuinely replaces testing every point; magenta is that membership test, green the divide-and-conquer cull.
FIG Honestly scoped: quickhull and monotone-chain can differ on whether collinear boundary points count as hull vertices, so the sphere canonicalizes to strict vertices before comparing — the convention is made explicit, not hidden. The extreme-point split, farthest-point recursion, strict-hull canonicalization, and monotone cross-check run in-browser and agree. The AVAN inverse is honest — culling interiors in bulk and recursing on the frontier genuinely replaces testing every point; magenta is that membership test, green the divide-and-conquer cull.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SHORTCUT · David Lee Wise (ROOT0), with AVAN