A k-d tree is a data structure used to search in
multidimensional
spaces often used in fields such as computer vision,
pattern
recognition, spatial database, astronomy...
A k-d tree is based on the very well known binary
search tree. Given a point set that lies in a k-dimensional space, the
general purpose of a k-d tree is to recursively partition the space into
cells such that each cell contains at most a certain number of input
data points.
Each interior node of the tree represents a
hyperplane chosen to be orthogonal to one of the k axes.
Each interior node has a left and a right subtree,
containing points located on either side of the hyperplane that this
interior node represents. Each leaf of the tree stores a non null data
set, usually a single point.
Much research and improvement has been done on the
original
k-d tree introduced by Bentley. Adaptive k-d tree,
semidynamic
k-d tree, local split decision, quad-tree/ oct-tree
are all
related to k-d tree. They differ from it by their
way of selecting hyperplanes, and the structure and meaning of interior
nodes and leaves, for achieving efficient storage and search time.
The images below show how the original k-d tree
(2-d tree in this case) partitions the plane, given this point
set:
