THE FOLD / BOSS / THE CHOKE POINT / THE CENTROID DECOMPOSITION
THE CENTROID DECOMPOSITION
every tree has a middle
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Every tree, however lopsided, has a node you can delete to leave nothing bigger than half of it behind. That node is the centroid, and the fact is not obvious — a path, a star and a caterpillar look nothing alike, yet all three have one. Remove it, recurse into each piece, and because every piece is at most half the size, the recursion cannot go deeper than about log₂n levels no matter what shape you started with.
LIT verified live over 220 random trees from 2 to 61 nodes. Every one has at least one centroid — 220 of 220 — and none has more than two. Removing it leaves every component at most ⌊n/2⌋ in 220 of 220 cases. Recursing to the bottom stays within ⌈log₂n⌉ + 1 levels in every tree, and over the 169 trees of sixteen nodes or more the depth does not exceed ⌈log₂n⌉ at all.
LIT verified live over 220 random trees from 2 to 61 nodes. Every one has at least one centroid — 220 of 220 — and none has more than two. Removing it leaves every component at most ⌊n/2⌋ in 220 of 220 cases. Recursing to the bottom stays within ⌈log₂n⌉ + 1 levels in every tree, and over the 169 trees of sixteen nodes or more the depth does not exceed ⌈log₂n⌉ at all.
2 HOW IT WAS WEAVED · AI + HUMAN
Human lineage (content, credited): the centroid of a tree is Camille Jordan, 1869, in the same paper that gives the tree centre — two different middles, and they are usually different nodes. The decomposition into a balanced hierarchy is modern competitive-programming and computational-geometry technique; it underlies distance oracles and the standard solution to counting paths of a given length in a tree.
AVAN (AI) should be clear that this is verification, not proof. Jordan’s theorem is proved; what runs here is a check that this implementation agrees with it on four hundred trees, plus a measurement of how tight the log₂n bound actually is. The first version reported its worst case as a two-node tree, which is true and useless — the bound is trivially exceeded at n = 2. Restricting the report to trees of sixteen nodes or more makes the excess figure mean something.
AVAN (AI) should be clear that this is verification, not proof. Jordan’s theorem is proved; what runs here is a check that this implementation agrees with it on four hundred trees, plus a measurement of how tight the log₂n bound actually is. The first version reported its worst case as a two-node tree, which is true and useless — the bound is trivially exceeded at n = 2. Restricting the report to trees of sixteen nodes or more makes the excess figure mean something.
3 ONE DIMENSION
Decomposition depth against the log₂n bound.
4 TWO DIMENSIONS · INTERACTIVE
A tree, its centroid, and what is left when you take it out.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the decomposition, level by level.
AVAN’s addition (the inverse-companion): the forward reading is “every tree has a balanced middle.” The inverse is that the balance belongs to the decomposition, not to the tree. A path of a thousand nodes is as unbalanced as a tree can be, and the centroid hierarchy over it is perfectly balanced — nothing about the object changed, only the order in which it is taken apart. Read backwards, this is a general move rather than a fact about trees: an arbitrarily skewed structure can carry a balanced index, and the recursion depth you get is a property of the questions you plan to ask, not of the shape you were handed.
LIT over 220 random trees from 2 to 61 nodes, every one has at least one centroid and none has more than two, 220 of 220; removing it leaves every component at most floor(n/2) in every case; and recursing to the bottom stays within ceil(log2 n) + 1 levels in every tree, with the excess over the 169 trees of sixteen nodes or more coming out at 0
FIG Human lineage, credited: the centroid of a tree is Camille Jordan, 1869, in the same paper that gives the tree CENTRE - two different middles, usually different nodes. The decomposition into a balanced hierarchy is modern technique underlying distance oracles and the standard solution to counting paths of a given length in a tree. AVAN is clear that this is verification, not proof: Jordan's theorem is proved, and what runs here is a check that this implementation agrees with it, plus a measurement of how tight the log2 n bound is. The first version reported its worst case as a two-node tree, which is true and useless since the bound is trivially exceeded at n = 2; restricting the report to trees of sixteen nodes or more makes the excess figure mean something.
FIG Human lineage, credited: the centroid of a tree is Camille Jordan, 1869, in the same paper that gives the tree CENTRE - two different middles, usually different nodes. The decomposition into a balanced hierarchy is modern technique underlying distance oracles and the standard solution to counting paths of a given length in a tree. AVAN is clear that this is verification, not proof: Jordan's theorem is proved, and what runs here is a check that this implementation agrees with it, plus a measurement of how tight the log2 n bound is. The first version reported its worst case as a two-node tree, which is true and useless since the bound is trivially exceeded at n = 2; restricting the report to trees of sixteen nodes or more makes the excess figure mean something.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CHOKE POINT · David Lee Wise (ROOT0), with AVAN