|Two figures showing a kd-tree.
The left one
shows the split lines around medians,
and the right figure show the actual kd-tree.
More info about kd-trees can be found in book :
M. de Berg, M.van Kreveld, M. Overmars, O.Schwarzkopf, "Computational Geometry (Algorithms and Applications) ", Springer, 1998.
|The algorithm used to build the
kd-tree in this
The bound for building a kd-tree
|The algorithm used in searching
The bound for searching a kd-tree is