# How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees:

Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction and hence eliminate the costly step of finding the median at each level of subdivision. [..] This algorithm presorts n points in each of k dimensions

I fail to understand how that is actually done. Consider this example:

Lets say I have 5 points in an array.

0 = (4, 7)
1 = (2, 9)
2 = (5, 4)
3 = (3, 6)
4 = (2, 1)


I suppose we now want to create 2 sorted arrays, one by X and one by Y ?

Sort them by X     Sort them by Y
1 = (2, 9)         4 = (2, 1)
4 = (2, 1)         2 = (5, 4)
3 = (3, 6)         3 = (3, 6)
0 = (4, 7)         0 = (4, 7)
2 = (5, 4)         1 = (2, 9)


We start creating the KD-Tree. Lets split by X axis, at the first step. We select the median of the points, 3 = (3, 6), so the Left and right trees will like this:

Left  (first half)
1 = (2, 9)
4 = (2, 1)

Right  (second half)
0 = (4, 7)
2 = (5, 4)


Now we want to sort the Left and the Right trees by Y axis. How are we supposed to make use of the points that we sorted previously by Y axis ?

The only solution in my eyes is to re-sort the Left and Right trees respectively, by Y axis. What is Wikipedia talking about ?

• (I hope the sentences following in the wikipedia article sum it up usefully: presorts n points in each of k dimensions using an O(n log n) sort […] prior to building the tree[, maintain] the order of these k presorts during tree construction and thereby [avoid] finding the median at each level of subdivision.) (From skimming the references given, I can't tell the connection to Havran V., Bittner J. "On improving k-d trees for ray shooting" (2002).) Apr 30, 2016 at 19:37
• Maybe you could try a z-ordering instead of median? Z-ordering (en.wikipedia.org/wiki/Z-order_curve) can be achieved by interleaving the bits of the coordinates. May 2, 2016 at 9:29
• (There is jcgt.org.) Apr 29, 2020 at 5:23
• Read the paper referred to by Wikipedia ! The sorts are made by means of $k$ indexes, and the points are left in place. Though it is true that the sorts need not be repeated, the cost is $O(n\log n)$, while the medians can be made in O(n) worst-case or expected case. So comparative benchmarking should be made. Apr 19 at 6:59