A set S of n points in k -dimensions. Construct a tree which partitions the space by half-planes such that each point is contained in it is own region. This provides a fast way to access any input object by position. We traverse down the hierarchy until we find the cell containing the object and then scan through the few objects in the cell to identify the right one.
Typical algorithms construct kd-trees by partitioning point sets.
These children are again partitioned into equal halves, using planes through a different dimension. Partitioning stops after lg n levels, with each point in its own leaf cell. Alternate kd-tree construction algorithms insert points incrementally and divide the appropriate cell, although such trees can become seriously unbalanced.