K-D Tree: ten thousand points, cut in half

Every picture in this series begins as ten thousand points scattered at random across a square. You never see the points. You only see where they were cut.

The algorithm

A k-d tree is a data structure that computer scientists use to search space quickly. Given a cloud of points, it answers questions like "which point is closest to here?" without checking every point. It works by dividing space in half again and again, so that the right half can be found in a few steps.

To build one in two dimensions:

1. Scatter the points and draw a box around them.
2. Find the median point, the one with as many points to its left as to its right, and cut the box with a vertical line through it.
3. Each half is now a box of its own. Cut each one at its median, this time horizontally.
4. Keep going, switching between vertical and horizontal at each level, until every box holds only a point or two.

Because every cut falls at a median, the two halves always hold the same number of points. That is the rule that gives the picture its character. Where the random scatter happens to be thin, cells come out large and open. Where points have crowded together, the cuts come close and the grid tightens. The pattern of rectangles is an exact map of the density of a cloud you can't see.

The tree is built level by level: one cut, then two, four, eight, and so on. The whole composition arrives coarse to fine.

Where it started

The first version, 2023. Each line is one cut of the tree.

I first made this in 2023 as a short Python notebook, adapted from Marcus Volz's R code in his mathart collection. It drew every cut as a single blue line on white, and that was the whole idea: the bare structure of the tree.

There is one accident in it that I like. The program stops after a fixed number of cuts, one fewer than the number of points. Ten thousand points don't fill a whole number of levels, so the last level is only partly finished when the program stops. Cuts are made in the order the tree visits its boxes, so the boxes visited first get one more level of detail than the rest. That is the denser patch in the upper left. It isn't a bug in the drawing. It shows the order the tree was built in.

From lines to cells

For the new works I turned the picture inside out. The original was about the lines: the cuts. These are about the cells: the rectangles the cuts leave behind.

The tree is rebuilt in Processing with the same median rule, now stopped at twelve levels, which leaves about four thousand cells. Then the lines are removed. Each cell is drawn as a solid block, shrunk slightly so a thin channel of bare paper runs between it and its neighbours. The grid is still there, but now it is made of absence: white streets between coloured lots.

Most cells take a pale wash of the palette. About one in seven, chosen by chance from the seed, takes full colour from a narrow ramp of three or four related hues. The palettes never span more than a quarter of the colour wheel, so the scatter reads as one family rather than confetti.

Nothing is placed by hand. The seed decides where every point falls, and so every cut, every cell and every coloured block. The same seed and settings always produce the same image, pixel for pixel, at any size. That is what makes it possible to find a composition in a small preview and then print it half a metre wide.

Summer 38

K-D Tree Summer 38. 50 × 50 cm.

Magenta, coral and orange on a blush ground. The ramp runs from deep magenta to marigold, and the pale cells take a wash of its pink midpoint, so the whole sheet is warm. The blocks are spaced a little wider apart here, so the paper channels are more visible and the surface reads as tiles.

Silence 39

K-D Tree Silence 39. 50 × 50 cm.

The same structure in a cool key: peacock, teal and lagoon on a grey-green ground. The gap between blocks is narrower, so the grid recedes and the coloured cells seem to float on the surface. It is the quieter of the two, hence the title.

The prints

Both works are open-edition prints at 50 × 50 cm, with a white paper margin carrying the title and number. They are available in my Etsy shop.

K-D Tree is made in Processing. The 2023 notebook it grew from was adapted from marcusvolz/mathart.