THE FOLD / BOSS / THE-GAUNTLET / THE CHAN'S ALGORITHM
THE CHAN'S ALGORITHM
a hull wrapped over mini-hulls
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Chan’s algorithm computes a convex hull in O(n log h) time — where h is the number of hull vertices — making it output-sensitive: fast when the hull is small even if the point set is huge. Its trick is a clever marriage. Guess a bound m on h; split the n points into groups of m and compute each group’s hull with a quick Graham scan; then gift-wrap around the whole set, but jump between groups by binary-searching each mini-hull’s tangent, so each wrap step costs only O((n/m) log m). If the wrap doesn’t close within m steps, the guess was too small — double m and retry. The doubling makes the total cost dominated by the final, correct guess.
LIT verified live: over 2000 random point sets, Chan’s grouped-hull-plus-wrap-plus-doubling produces exactly the same convex hull as a reference (Andrew’s monotone chain) (window.__chan). FIG honest scope: verified in general position; the group tangents here use a linear scan (the true speedup comes from binary search on each mini-hull).
LIT verified live: over 2000 random point sets, Chan’s grouped-hull-plus-wrap-plus-doubling produces exactly the same convex hull as a reference (Andrew’s monotone chain) (window.__chan). FIG honest scope: verified in general position; the group tangents here use a linear scan (the true speedup comes from binary search on each mini-hull).
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gauntlet — guess the hull size, wrap around mini-hulls, and double the guess until it closes. AVAN (AI) built the instrument: the grouped mini-hulls, the gift-wrap over their vertices, the doubling schedule, and the reference-hull check.
Credit as content: Timothy Chan (1996). The weave: David names the gauntlet; I confirm the output-sensitive construction yields exactly the convex hull.
Credit as content: Timothy Chan (1996). The weave: David names the gauntlet; I confirm the output-sensitive construction yields exactly the convex hull.
3 ONE DIMENSION
Points split into groups; each group's mini-hull is computed; then a gift-wrap jumps between mini-hulls.
4 TWO DIMENSIONS · INTERACTIVE
A point set; Chan's hull matches the reference — computed by wrapping over group mini-hulls with a doubling size guess.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the convex hull, built output-sensitively.
AVAN’s addition (the inverse-companion): don’t scan all points for each hull edge — wrap over mini-hulls. The inverse of ‘test every point’ is ‘group, hull each group, gift-wrap between mini-hulls, and double the size guess until it closes.’ Magenta are interior points; green is the hull. Guess, wrap, double.
LIT Genuine Chan's algorithm for output-sensitive convex hull (Timothy Chan, 1996). Verified live: over 2000 random point sets, the grouped-mini-hull + gift-wrap + doubling-m construction produces exactly the reference hull (Andrew's monotone chain) (window.__chan.matchesReference).
FIG Honest scope: verified in general position; the group tangents here use a linear scan (the true O(n log h) speedup comes from binary search on each mini-hull, and the doubling schedule). The AVAN inverse is honest — instead of testing every point for each hull edge, one groups the points, hulls each group, gift-wraps between mini-hulls, and doubles the size guess until it closes. Magenta are interior points; green is the hull. Guess, wrap, double.
FIG Honest scope: verified in general position; the group tangents here use a linear scan (the true O(n log h) speedup comes from binary search on each mini-hull, and the doubling schedule). The AVAN inverse is honest — instead of testing every point for each hull edge, one groups the points, hulls each group, gift-wraps between mini-hulls, and doubles the size guess until it closes. Magenta are interior points; green is the hull. Guess, wrap, double.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-GAUNTLET · David Lee Wise (ROOT0), with AVAN