space-filling tree
{{Short description|An assembly of curves that branch out from a root to reach every point in a space}}
Space-filling trees are geometric constructions that are analogous to space-filling curves,Sagan, H. and J. Holbrook: "Space-filling curves", Springer-Verlag, New York, 1994 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.Kuffner, J. J. and S. M. LaValle: Space-filling Trees, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.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 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).{{cite book| url= https://books.google.com/books?id=xJ4qiEBNP4gC |title= The Fractal Geometry of Nature |archiveurl= https://web.archive.org/web/20151130231048/https://books.google.com/books?id=xJ4qiEBNP4gC&printsec=frontcover |archivedate=30 November 2015 | first= Benoît| last= Mandelbrot| publisher= W H Freeman & Co| year= 1982 |isbn= 0-7167-1186-9}} The concept was made more rigorous and given the name "space-filling tree" in a 2009 tech report Kuffner, J. J. and S. M. LaValle: Space-filling Trees, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009. 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 as a "sequence of trees", then states " 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 . At each iteration, additional branches are added to the existing trees.
Image:Space_Filling_Tree_Square1.png|Square space-filling tree (Iteration 1)
Image:Space_Filling_Tree_Square2.png|Square space-filling tree (Iteration 2)
Image:Space_Filling_Tree_Square3.png|Square space-filling tree (Iteration 3)
Image:Space_Filling_Tree_Square4.png|Square space-filling tree (Iteration 4)
Image:Space_Filling_Tree_Square5.png|Square space-filling tree (Iteration 5)
Image:Space_Filling_Tree_Square6.png|Square space-filling tree (Iteration 6)
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.
Image:Space_Filling_Tree_Tri_iter_1_2_3.png|Subdivision scheme for the first three iterations of the triangle space-filling tree
The first six iterations of the triangle space-filling tree are illustrated below:
Image:Space_Filling_Tree_Tri1.png|Triangle space-filling tree (Iteration 1)
Image:Space_Filling_Tree_Tri2.png|Triangle space-filling tree (Iteration 2)
Image:Space_Filling_Tree_Tri3.png|Triangle space-filling tree (Iteration 3)
Image:Space_Filling_Tree_Tri4.png|Triangle space-filling tree (Iteration 4)
Image:Space_Filling_Tree_Tri5.png|Triangle space-filling tree (Iteration 5)
Image:Space_Filling_Tree_Tri6.png|Triangle space-filling tree (Iteration 6)
Space-filling trees can also be constructed in higher dimensions. The simplest examples are cubes in and hypercubes in .
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 is illustrated below:
Image:Space_Filling_Tree_Cube3.png|Cube space-filling tree (Iteration 3)