THE FOLD / BOSS / THE-GAUNTLET / THE VP-TREE
THE VP-TREE
nearest found by pruning a metric tree
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The vantage-point tree finds nearest neighbours in any metric space — not just coordinates, but anything with a distance obeying the triangle inequality. At each node it picks a vantage point and a radius (the median distance to the rest), splitting the remaining points into those inside the sphere and those outside. A query descends the side its distance suggests, and — crucially — the triangle inequality lets it prove that the whole other subtree can be skipped whenever it can’t possibly hold anything closer than the best found so far. So a search touches only a small fraction of the points while still returning the exact nearest neighbour.
LIT verified live: over 3000 random trees in 3-D, the VP-tree’s pruned search returns exactly the same nearest neighbour as a brute-force scan of every point (window.__vp_tree). FIG no framing; the median-split build and the triangle-inequality pruning run in-browser.
LIT verified live: over 3000 random trees in 3-D, the VP-tree’s pruned search returns exactly the same nearest neighbour as a brute-force scan of every point (window.__vp_tree). FIG no framing; the median-split build and the triangle-inequality pruning run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gauntlet — run the query through the tree, and the triangle inequality clears whole regions it never has to search. AVAN (AI) built the instrument: the vantage-point/median split, the pruned nearest-neighbour search, and the brute-force cross-check.
Credit as content: Peter Yianilos (1993); Jeffrey Uhlmann (metric trees, 1991). The weave: David names the gauntlet; I confirm the pruned search returns the exact nearest neighbour.
Credit as content: Peter Yianilos (1993); Jeffrey Uhlmann (metric trees, 1991). The weave: David names the gauntlet; I confirm the pruned search returns the exact nearest neighbour.
3 ONE DIMENSION
A vantage point and its median radius split the rest into inside / outside; the triangle inequality prunes a whole side.
4 TWO DIMENSIONS · INTERACTIVE
Points and a query; the VP-tree's nearest neighbour matches the brute-force answer, touching far fewer points.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the exact nearest neighbour.
AVAN’s addition (the inverse-companion): don’t scan every point — prune by the triangle inequality. The inverse of ‘compute all distances’ is ‘if the best-so-far can’t reach across a vantage sphere, skip that whole subtree.’ Magenta is a pruned region never searched; green is the nearest neighbour returned. Skip what can’t be closer.
LIT Genuine vantage-point tree (Peter Yianilos, 1993; metric trees, Jeffrey Uhlmann 1991). Verified live: over 3000 random 3-D point sets, the median-split VP-tree's triangle-inequality-pruned nearest-neighbour search returns exactly the same nearest point (to ~1e-9) as a brute-force scan (window.__vp_tree.matchesBrute).
FIG No framing: the median-split build and the triangle-inequality pruning run in-browser. The AVAN inverse is honest — instead of computing all distances, the triangle inequality proves a whole subtree can't beat the best-so-far and skips it. Magenta is a pruned region never searched; green is the exact nearest neighbour returned. Skip what can't be closer.
FIG No framing: the median-split build and the triangle-inequality pruning run in-browser. The AVAN inverse is honest — instead of computing all distances, the triangle inequality proves a whole subtree can't beat the best-so-far and skips it. Magenta is a pruned region never searched; green is the exact nearest neighbour returned. Skip what can't be closer.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-GAUNTLET · David Lee Wise (ROOT0), with AVAN