THE FOLD / GLITCH / STACK OVERFLOW / THE QUADTREE
THE QUADTREE
quarter the plane recursively to query it fast
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A point-region quadtree indexes 2D points by recursively quartering the plane. Each node holds a small bucket of points; when it overflows, it splits into four children (NW, NE, SW, SE), redistributing its points. To answer a range query — which points fall in a rectangle? — you descend only into the children whose regions intersect the query, skipping vast empty or far-away quadrants. Sparse regions cost nothing to search.
LIT verified live: over 1000 random point sets and query rectangles, the quadtree returns exactly the same points as a brute-force scan of every point (window.__quadtree). FIG no framing; exact set comparison.
LIT verified live: over 1000 random point sets and query rectangles, the quadtree returns exactly the same points as a brute-force scan of every point (window.__quadtree). FIG no framing; exact set comparison.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at stack-overflow — the recursion that quarters space again and again; a quadtree is that recursion made a spatial index, each split a deeper frame. AVAN (AI) built the instrument: the capacity-triggered subdivision into four, the region-intersection pruning for range queries, and the match against a brute scan.
Credit as content: Raphael Finkel & Jon Bentley (1974). The weave: David names stack-overflow; I quarter the plane recursively as points accumulate, answer range queries by descending only into intersecting quadrants, and confirm the results exactly match scanning every point — fewer comparisons, same answer.
Credit as content: Raphael Finkel & Jon Bentley (1974). The weave: David names stack-overflow; I quarter the plane recursively as points accumulate, answer range queries by descending only into intersecting quadrants, and confirm the results exactly match scanning every point — fewer comparisons, same answer.
3 ONE DIMENSION
Overflow a node → split into NW, NE, SW, SE and redistribute. A range query visits only quadrants overlapping the query rectangle — empty and distant ones are skipped whole.
4 TWO DIMENSIONS · INTERACTIVE
Points with the quadtree’s subdivisions and a query rectangle; the returned points checked against a brute scan.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: fast range queries by quartering space.
AVAN’s addition (the inverse-companion): answer ‘which points are in this box?’ without testing every point — recursively quarter the plane and descend only into quadrants that intersect the query. The inverse of ‘scan all n points’ is ‘prune whole empty quadrants — visit only what overlaps.’ Magenta is the full linear scan; green is the pruned descent. Space carved so the search stays small.
LIT Genuine point-region quadtree (Raphael Finkel & Jon Bentley 1974). Verified live: over 1000 random point sets and query rectangles, the capacity-triggered four-way subdivision with region-intersection pruning returns exactly the point set a brute-force scan of every point returns (window.__quadtree.matchesBrute).
FIG No framing: the capacity-triggered subdivision into four, the region-intersection pruning for range queries, and the match against a brute scan run in-browser with exact set comparison and agree. The AVAN inverse is honest — answering 'which points are in this box?' by descending only into intersecting quadrants genuinely replaces scanning all n points; magenta is the full linear scan, green the pruned descent. Space carved so the search stays small.
FIG No framing: the capacity-triggered subdivision into four, the region-intersection pruning for range queries, and the match against a brute scan run in-browser with exact set comparison and agree. The AVAN inverse is honest — answering 'which points are in this box?' by descending only into intersecting quadrants genuinely replaces scanning all n points; magenta is the full linear scan, green the pruned descent. Space carved so the search stays small.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of STACK OVERFLOW · David Lee Wise (ROOT0), with AVAN