Kd-Tree Applet Demo Page

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.

kdtree image
The algorithm used to build the kd-tree in this
demonstration.

The bound for building a kd-tree
is O(nlogn).


kdtree build algorithm
The algorithm used in searching in this
demonstration.

The bound for searching a kd-tree is
O(sqrt(n)).
kstree search algorithm