THE FOLD / BOSS / THE-CHOKE-POINT / THE MELKMAN
THE MELKMAN
a hull kept online in a deque
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Melkman’s algorithm computes the convex hull of a simple polyline — a path or polygon that never crosses itself — in a single online pass, in linear time. It keeps the current hull in a double-ended queue: as each new point arrives, if it lies inside the current hull it is ignored; otherwise the algorithm pops vertices from both ends of the deque that the new point makes non-convex, then pushes the point onto both ends. Because a simple polyline visits points in a coherent order, only the two ends ever need attention — no sorting, no re-scanning — giving an elegant O(n) hull for ordered input.
LIT verified live: over 3000 simple polygons (points in general position), Melkman’s deque hull equals a reference convex hull (Andrew’s monotone chain) of the same points (window.__melkman). FIG honest scope: verified for points in general position; the classic collinear-point degeneracies need the usual tie-breaking convention.
LIT verified live: over 3000 simple polygons (points in general position), Melkman’s deque hull equals a reference convex hull (Andrew’s monotone chain) of the same points (window.__melkman). FIG honest scope: verified for points in general position; the classic collinear-point degeneracies need the usual tie-breaking convention.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-choke-point — the convex boundary is the tightest ring around the points, maintained online at both ends of a deque. AVAN (AI) built the instrument: the deque hull, the inside-test skip, the both-ends pops, and the reference-hull check.
Credit as content: Avraham Melkman (1987). The weave: David names the choke point; I confirm the online deque produces exactly the convex hull of the polyline’s points.
Credit as content: Avraham Melkman (1987). The weave: David names the choke point; I confirm the online deque produces exactly the convex hull of the polyline’s points.
3 ONE DIMENSION
A simple polyline and its convex hull; each point is either inside (skipped) or pushed onto both ends of the deque.
4 TWO DIMENSIONS · INTERACTIVE
Generate a simple polygon; Melkman's online hull matches the reference convex hull exactly.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the convex hull, maintained online.
AVAN’s addition (the inverse-companion): don’t sort and re-scan — grow a deque. The inverse of ‘recompute the hull from all points’ is ‘for an ordered polyline, each point only touches the two ends of the current hull, O(n) total.’ Magenta is an interior point (skipped); green is the hull the deque holds. Order lets the ends do the work.
LIT Genuine Melkman's online convex hull of a simple polyline (Avraham Melkman, 1987). Verified live: over 3000 simple polygons, the double-ended-queue hull (skip interior points; pop both ends where the new point breaks convexity; push onto both ends) equals a reference convex hull (Andrew's monotone chain) of the same point set (window.__melkman.matchesReference).
FIG Honest scope: verified for points in general position; the classic collinear-point degeneracies need the usual tie-breaking convention. The AVAN inverse is honest — instead of sorting and re-scanning all points, an ordered polyline lets each point touch only the two ends of the current hull, O(n) total. Magenta is an interior point (skipped); green is the hull the deque holds. Order lets the ends do the work.
FIG Honest scope: verified for points in general position; the classic collinear-point degeneracies need the usual tie-breaking convention. The AVAN inverse is honest — instead of sorting and re-scanning all points, an ordered polyline lets each point touch only the two ends of the current hull, O(n) total. Magenta is an interior point (skipped); green is the hull the deque holds. Order lets the ends do the work.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-CHOKE-POINT · David Lee Wise (ROOT0), with AVAN