k-d Trees

Early structure used for indexing in multiple dimensions. The k-d tree is used to store k-dimensional points data. For example Image may have many attributes such as spatial position, texture, color. So k-d trees can be used to represent such data. Data in this setion taken from [1].

Figure 2.1: Division of points by k-d Tree

[width=13cm]k-d.png

Purpose is always to hierarchically decompose space into a relatively small number of cells such that no cell contains too many input objects. 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. Each node in the tree is defined by a plane through one of the dimensions that partitions the set of points into left/right (or up/down) sets, each with half the points of the parent node. 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.