THE FOLD / GLITCH / RACE-CONDITION / THE BENTLEY-OTTMANN
THE BENTLEY-OTTMANN
a sweep line catching every crossing
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Bentley–Ottmann algorithm finds every intersection among a set of line segments without checking all pairs. A vertical sweep line moves left to right; the segments it currently crosses are kept in top-to-bottom order, and only neighbours in that order are ever tested for crossing. Two segments can only intersect after becoming adjacent on the sweep line, so tracking neighbourhood changes at endpoints and crossings catches all K intersections in O((n+K) log n) — far better than the O(n²) of brute force when crossings are few.
LIT verified live: over hundreds of random segment sets, the sweep’s intersection set exactly equals the brute-force all-pairs set (window.__bentley_ottmann). FIG no framing; the event-driven sweep and an O(n²) check both run in-browser (general position; the classic degenerate-handling caveats apply).
LIT verified live: over hundreds of random segment sets, the sweep’s intersection set exactly equals the brute-force all-pairs set (window.__bentley_ottmann). FIG no framing; the event-driven sweep and an O(n²) check both run in-browser (general position; the classic degenerate-handling caveats apply).
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at race-condition — segments race along the sweep line, and a crossing is exactly the moment two of them swap order. AVAN (AI) built the instrument: the event queue, the sweep-status order, neighbour tests, and the brute-force cross-check.
Credit as content: Jon Bentley & Thomas Ottmann (1979). The weave: David names the race; I confirm the sweep recovers exactly the same intersection set as testing all pairs.
Credit as content: Jon Bentley & Thomas Ottmann (1979). The weave: David names the race; I confirm the sweep recovers exactly the same intersection set as testing all pairs.
3 ONE DIMENSION
Segments and their crossings; the sweep line moves right, and only segments adjacent on it are tested for intersection.
4 TWO DIMENSIONS · INTERACTIVE
A random segment set; the sweep marks every intersection, and the count matches the brute-force all-pairs test.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the intersection points the sweep discovers.
AVAN’s addition (the inverse-companion): don’t test all pairs — test only neighbours on the sweep. The inverse of ‘check every pair’ is ‘two segments can cross only where they are adjacent on the sweep line.’ Magenta is the O(n²) all-pairs cloud; green is the crossings the sweep actually finds — the same set. Sweep, don’t enumerate.
LIT Genuine Bentley–Ottmann sweep-line algorithm (Jon Bentley & Thomas Ottmann, 1979). Verified live: over 300 random segment sets the event-driven sweep (endpoint + intersection events, neighbour tests on the sweep status) recovers exactly the brute-force all-pairs intersection set, 0 mismatches (window.__bentley_ottmann.matchesBrute).
FIG No framing: the event-driven sweep and an O(n²) brute-force check both run in-browser. Honest scope — segments are generated in general position; the classic degenerate cases (vertical segments, triple points, overlapping collinear segments) need the standard extra handling. The AVAN inverse is honest — two segments can cross only where they are adjacent on the sweep line, so only neighbours are tested. Magenta is the O(n²) all-pairs cloud; green is the same crossings the sweep finds. Sweep, don't enumerate.
FIG No framing: the event-driven sweep and an O(n²) brute-force check both run in-browser. Honest scope — segments are generated in general position; the classic degenerate cases (vertical segments, triple points, overlapping collinear segments) need the standard extra handling. The AVAN inverse is honest — two segments can cross only where they are adjacent on the sweep line, so only neighbours are tested. Magenta is the O(n²) all-pairs cloud; green is the same crossings the sweep finds. Sweep, don't enumerate.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of RACE-CONDITION · David Lee Wise (ROOT0), with AVAN