QuickNeighborhood

Nov 2007 · age 25

What it was

A one-file algorithm study with a single question: among ten thousand random points in a unit cube, which pairs sit within radius r of each other, and can you find them without comparing all fifty million pairs or building a grid or a tree? Jeff's answer was to cut the point set with a plane and sort every point into four bands by signed distance: far below, just below, just above, far above. Pairs inside one half are found by recursing on that half. Pairs that cross the plane can only come from the two thin inner bands, so a second routine splits those two slabs again and pairs only adjacent bands. A counting sort does the partition in place. A benchmark counted distance tests rather than seconds, and the whole thing was published as one C++ file under an MIT licence.

Wins, for the age

• At twenty-five, in evening sessions while cofounding a startup, Jeff found on their own the same seam argument behind the classic divide-and-conquer closest-pair algorithm of 1975, and pushed it further with four bands instead of two.
• Replaced the tree with an in-place counting sort and recursion on array ranges, so there was no allocation per level at all.
• Judged the algorithm by operations performed as a fraction of the brute-force worst case. A mammal with a stopwatch chose to count comparisons instead, which is the more honest instrument.
• Shipped it as a readable single file with its own benchmark and licence, meant for other people to read.

What it taught

• Arguing about cost by counting work, then checking the argument with a harness, became the default way to evaluate an algorithm.
• Reasoning about which partitions can possibly interact, the same argument that sits behind sweep-and-prune and bounding-slab tests.
• A k-d style split does not need a tree if you sort in place and recurse on ranges.
• Leftover code ships if nothing runs the debug build: the release freed static arrays it never allocated, and a degenerate splitting plane could recurse until the stack gave out.

Genealogy

Ancestors: none on record. It stands alone, a single evening's idea finished at dawn. Descendants: none on record. The write-up it was meant to become never arrived.

Epitaph

Here lies QuickNeighborhood, which proved its point in comparisons counted and then freed memory it never owned.