In contrast to space-filling curves, individual paths in the tree are short, allowing any part of the space to be quickly reached from the root.
[2][3] The simplest examples of space-filling trees have a regular, self-similar, fractal structure, but can be generalized to non-regular and even randomized/Monte-Carlo variants (see Rapidly exploring random tree).
Space-filling trees have interesting parallels in nature, including fluid distribution systems, vascular networks, and fractal plant growth, and many interesting connections to L-systems in computer science.
The concept of a "space-filling tree" in this sense was described in Chapter 15 of Mandelbrot's influential book The Fractal Geometry of Nature (1982).
It is not space-filling in the standard sense of including the entire 2-dimensional unit square.
Instead, the paper defines it as having trees in the sequence coming arbitrarily close to every point.
The standard term for this concept is that it includes a set of points that is dense everywhere in the unit square.
The simplest example of a space-filling tree is one that fills a square planar region.
Space-filling trees can also be defined for a variety of other shapes and volumes.
A similar sequence of iterations used for the square space-filling tree can be used for hypercubes.