THE FOLD / CO-OP / SPLIT SCREEN / THE LI CHAO TREE
THE LI CHAO TREE
the lowest line at any x, in log time
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Li Chao tree maintains a set of lines and answers “which line is lowest at this x?” in O(log) time — it stores the lower envelope of a pencil of lines. Each node owns the line that dominates the middle of its x-range; a new line either replaces it or is pushed to the half where it might win. It powers the convex-hull trick for speeding up dynamic programming, turning O(n2) DP transitions into O(n log n).
LIT verified live: over 200 trees, the Li Chao query returns exactly the minimum of all inserted lines at each x, matching a brute-force scan (window.__lichao). FIG no framing; exact.
LIT verified live: over 200 trees, the Li Chao query returns exactly the minimum of all inserted lines at each x, matching a brute-force scan (window.__lichao). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at split-screen — the many lines drawn at once, of which only the lowest at each point is seen. The Li Chao tree keeps that lower envelope. AVAN (AI) built the instrument: the recursive dominate-the-midpoint insertion, the descend-to-the-winning-half push, the log-time query, and the brute-minimum cross-check.
Credit as content: Li Chao (the segment-tree-of-lines technique). The weave: David names split-screen; I insert each line so the node keeps whichever dominates its midpoint and pushes the other down, and confirm the query returns the true minimum line at every x.
Credit as content: Li Chao (the segment-tree-of-lines technique). The weave: David names split-screen; I insert each line so the node keeps whichever dominates its midpoint and pushes the other down, and confirm the query returns the true minimum line at every x.
3 ONE DIMENSION
Many lines; at each x only the lowest matters. Their lower envelope is a piecewise-linear convex curve. A Li Chao tree stores it so any x-query returns the winning line in O(log) time.
4 TWO DIMENSIONS · INTERACTIVE
A set of lines and their lower envelope; query any x and compare the Li Chao result to a brute minimum.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the lower envelope of a pencil of lines.
AVAN’s addition (the inverse-companion): answer “lowest line at x” in O(log) by storing lines in a tree where each node keeps whichever dominates its midpoint and pushes the loser to the half it might still win. The inverse of ‘scan every line at every query’ is ‘keep the lower envelope in a tree — query in log time.’ Magenta is the linear scan per query avoided; green is the stored envelope. The minimum line, in log time.
LIT Genuine Li Chao tree (the segment-tree-of-lines technique). Verified live: over 200 trees with random lines and queries, the recursive dominate-the-midpoint insertion and log-time query return exactly the minimum of all inserted lines at each x, matching a brute-force scan (window.__lichao.matchesBrute).
FIG No framing: the recursive dominate-the-midpoint insertion, the descend-to-the-winning-half push, the log-time query, and the brute-minimum cross-check run in-browser and agree exactly. The AVAN inverse is honest — keeping at each node whichever line dominates its midpoint and pushing the loser to the half it might still win stores the lower envelope for O(log) queries; magenta is the linear scan per query avoided, green the stored envelope. The minimum line, in log time.
FIG No framing: the recursive dominate-the-midpoint insertion, the descend-to-the-winning-half push, the log-time query, and the brute-minimum cross-check run in-browser and agree exactly. The AVAN inverse is honest — keeping at each node whichever line dominates its midpoint and pushing the loser to the half it might still win stores the lower envelope for O(log) queries; magenta is the linear scan per query avoided, green the stored envelope. The minimum line, in log time.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SPLIT SCREEN · David Lee Wise (ROOT0), with AVAN