Space-filling tree explained

Space-filling trees are geometric constructions that are analogous to space-filling curves,^[1] but have a branching, tree-like structure and are rooted. A space-filling tree is defined by an incremental process that results in a tree for which every point in the space has a finite-length path that converges to it. 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.

Definition

A space-filling tree is defined by an iterative process whereby a single point in a continuous space is connected via a continuous path to every other point in the space by a path of finite length, and for every point in the space, there is at least one path that converges to it.

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).^[4] The concept was made more rigorous and given the name "space-filling tree" in a 2009 tech report ^[5] that defines "space-filling" and "tree" differently than their traditional definitions in mathematics. As explained in the space-filling curve article, in 1890, Peano found the first space-filling curve, and by Jordan's 1887 definition, which is now standard, a curve is a single function, not a sequence of functions. The curve is "space filling" because it is "a curve whose range contains the entire 2-dimensional unit square" (as explained in the first sentence of space-filling curve).

In contrast, a space-filling tree, as defined in the tech report, is not a single tree. It is only a sequence of trees. The paper says "A space-filling tree is actually defined as an infinite sequence of trees". It defines

T _{square} as a "sequence of trees", then states "T _{square} is a space-filling tree". 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. It states "A tree sequence T is called 'space filling' in a space X if for every x ∈ X, there exists a path in the tree that starts at the root and converges to x.". The standard term for this concept is that it includes a set of points that is dense everywhere in the unit square.

Examples

The simplest example of a space-filling tree is one that fills a square planar region. The images illustrate the construction for the planar region

[ 0 , 1 ] ^{2} \subset R ^{2} . At each iteration, additional branches are added to the existing trees.

Space-filling trees can also be defined for a variety of other shapes and volumes.Below is the subdivision scheme used to define a space-filling for a triangular region.At each iteration, additional branches are added to the existing trees connecting the center of each triangle to the centers of the four subtriangles.

The first six iterations of the triangle space-filling tree are illustrated below:

Space-filling trees can also be constructed in higher dimensions. The simplest examples are cubes in

R ^{3} and hypercubes in R ^{n} .A similar sequence of iterations used for the square space-filling tree can be used for hypercubes. The third iteration of such a space-filling tree in R ^{3} is illustrated below:

See also

• H tree

• Space-filling curve

• Rapidly exploring random tree (RRTs)

• Binary space partitioning

References

1. Sagan, H. and J. Holbrook: "Space-filling curves", Springer-Verlag, New York, 1994
2. Kuffner, J. J. and S. M. LaValle: Space-filling Trees, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.
3. Kuffner, J. J.; LaValle, S.M.; "Space-filling trees: A new perspective on incremental search for motion planning", 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), vol., no., pp.2199-2206, 25-30 Sept. 2011
4. Book: Mandelbrot, Benoît. The Fractal Geometry of Nature . https://web.archive.org/web/20151130231048/https://books.google.com/books?id=xJ4qiEBNP4gC&printsec=frontcover . 30 November 2015 . W H Freeman & Co. 1982 . 0-7167-1186-9.
5. Kuffner, J. J. and S. M. LaValle: Space-filling Trees, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.