THE FOLD / CHEAT / THE SPEEDRUN / THE ROTATING CALIPERS
THE ROTATING CALIPERS
polygon diameter in O(n) — only antipodal pairs matter
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Rotating calipers finds the diameter of a convex polygon — the farthest-apart pair of vertices — in O(n) instead of checking all O(n²) pairs. Picture two parallel lines (calipers) gripping the polygon on opposite sides, then rotate them together around the shape: the farthest pair is always a pair of antipodal vertices touched by the calipers, and you sweep through all of them in one loop.
The same technique gives the width, the minimum-area bounding box, and the closest distance between two convex polygons.
LIT verified live: over 200 random convex hulls, the diameter found by rotating calipers equals the brute-force maximum over all vertex pairs, every time (window.__rotatingcalipers). FIG no framing; exact computational geometry.
The same technique gives the width, the minimum-area bounding box, and the closest distance between two convex polygons.
LIT verified live: over 200 random convex hulls, the diameter found by rotating calipers equals the brute-force maximum over all vertex pairs, every time (window.__rotatingcalipers). FIG no framing; exact computational geometry.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-speedrun — the same result reached in a fraction of the moves. Rotating calipers is a speedrun of the diameter: O(n²) pairs collapse to one O(n) rotation. AVAN (AI) built the instrument: the convex hull, the antipodal caliper sweep, the brute-force cross-check.
Credit as content: Michael Shamos (1978, diameter, in his thesis); named and generalised by Godfried Toussaint (1983). The weave: David names the speedrun; I wrap the points in a hull, rotate the calipers to the farthest antipodal pair, and confirm it matches the exhaustive maximum.
Credit as content: Michael Shamos (1978, diameter, in his thesis); named and generalised by Godfried Toussaint (1983). The weave: David names the speedrun; I wrap the points in a hull, rotate the calipers to the farthest antipodal pair, and confirm it matches the exhaustive maximum.
3 ONE DIMENSION
Two parallel calipers gripping the hull, rotating together. As they turn, the vertices they touch trace out the antipodal pairs — the only candidates for the farthest distance.
4 TWO DIMENSIONS · INTERACTIVE
Scatter points, wrap them in a convex hull, and rotate the calipers to find the diameter (drawn as the longest chord). Verify it equals the brute-force maximum over all pairs.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the hull with its antipodal pairs highlighted, the diameter the longest among them.
AVAN’s addition (the inverse-companion): you never need all O(n²) pairs, because the farthest pair must be antipodal — each of the two points has a tangent line parallel to the other’s, so they are gripped by the calipers at opposite ends. And antipodal pairs number only O(n). The inverse of ‘check every pair’ is ‘check only the O(n) antipodal ones, because the extreme always lives on the boundary of the boundary.’ Convexity is what guarantees it: on a convex hull, the maximum distance is supported by parallel tangents. Magenta is the cloud of O(n²) pairs the calipers skip; green is the O(n) antipodal pairs they visit, one of which is the true diameter. The answer hides only among tangent-supported pairs.
LIT Genuine rotating calipers (Shamos 1978, diameter; named/generalized by Toussaint 1983). Verified live: over 200 random point sets, Andrew's monotone-chain convex hull plus an antipodal caliper sweep returns a diameter that equals the brute-force maximum squared-distance over all hull vertex pairs, every time (window.__rotatingcalipers.diameterMatchesBrute).
FIG No framing: the convex hull, the antipodal caliper sweep, and the brute-force cross-check run in-browser and are exact. The AVAN inverse is honest — the farthest pair must be antipodal (supported by parallel tangents) and antipodal pairs number only O(n); magenta is the O(n^2) pairs skipped, green the O(n) antipodal pairs holding the diameter.
FIG No framing: the convex hull, the antipodal caliper sweep, and the brute-force cross-check run in-browser and are exact. The AVAN inverse is honest — the farthest pair must be antipodal (supported by parallel tangents) and antipodal pairs number only O(n); magenta is the O(n^2) pairs skipped, green the O(n) antipodal pairs holding the diameter.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SPEEDRUN · David Lee Wise (ROOT0), with AVAN