The simulation builds a k-d tree over a set of 2D points, drawing each recursive split as a line across the plane, then lets you place a query point and watch the search descend the tree, backtrack, and prune branches that cannot possibly contain a closer point than the current best.
Add or randomize a set of points to build the tree, click anywhere to drop a query point, and step through the search to see which branches get explored and which get pruned, with the current best distance shown as an expanding circle around the query.
Point set randomize/add, query point placement, step-through search play/pause, reset tree
K-d trees were introduced by Jon Bentley in 1975, and although the pruning-based search can be dramatically faster than brute force in low dimensions, its average query cost creeps back toward O(n) once the number of dimensions climbs into the hundreds, a limitation known as the curse of dimensionality.
The simulation builds a k-d tree over a set of 2D points, drawing each recursive split as a line across the plane, then lets you place a query point and watch the search descend the tree, backtrack, and prune branches that cannot possibly contain a closer point than the current best.
The simulation builds a k-d tree over a set of 2D points, drawing each recursive split as a line across the plane, then lets you place a query point and watch the search descend the tree, backtrack, and prune branches that cannot possibly contain a closer point than the current best.
Add or randomize a set of points to build the tree, click anywhere to drop a query point, and step through the search to see which branches get explored and which get pruned, with the current best distance shown as an expanding circle around the query.
K-d trees were introduced by Jon Bentley in 1975, and although the pruning-based search can be dramatically faster than brute force in low dimensions, its average query cost creeps back toward O(n) once the number of dimensions climbs into the hundreds, a limitation known as the curse of dimensionality.