K-d Tree Algorithm

A k-d tree is a space-partitioning binary tree data structure for organizing points in a k-dimensional space, invented by Jon Louis Bentley in 1975. Every node in the tree represents one k-dimensional point, and every non-leaf node implicitly defines a splitting hyperplane, usually chosen along one coordinate axis at a time in rotation, that divides the remaining space in two, with points on one side of the hyperplane stored in the left subtree and points on the other side stored in the right subtree. Built with median splits the tree stays balanced and supports nearest-neighbor and range searches in roughly logarithmic time on average, which makes k-d trees a standard structure for spatial queries in computer graphics, robotics and computational geometry, although their search performance degrades as the number of dimensions grows large, a limitation generally known as the curse of dimensionality.