K-D Tree Nearest Neighbors (k-NN)

k-d tree nearest neighbors search (k-NN). The red dots are the 10 nearest neighbors. Orange dots are scanned and not selected.

Compare with this block that implements a k nearest neighbor search using a quadtree instead of a k-d tree.

The algorithm for this search came from this course handout. Note that the “k” in k-d tree need not be the same number as the “k” in the k-NN search. This is just the letter used to denote a positive integer for both algorithms.