Space-filling tree
Encyclopedia
Space-filling trees are geometric constructions that are analogous to space-filling curve
s, 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 curve
s, individual paths in the tree are short, allowing any part of the space to be quickly reached from the root. 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-system
s in computer science.
to it.
The term "space-filling tree" in this sense was created in a 2009 tech report 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 in 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.
planar region. The images illustrate the construction for the planar region
. 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
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:
Space-filling curve
In mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square...
s, 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 curve
Space-filling curve
In mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square...
s, individual paths in the tree are short, allowing any part of the space to be quickly reached from the root. The simplest examples of space-filling trees have a regular, self-similar, fractal
Fractal
A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
structure, but can be generalized to non-regular and even randomized/Monte-Carlo
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
variants (see Rapidly-exploring random tree
Rapidly-exploring random tree
A Rapidly-exploring random tree is a data structure and algorithm designed for efficiently searching nonconvex, high-dimensional search spaces. The tree is constructed in such a way that any sample in the space is added by connecting it to the closest sample already in the tree.RRTs, developed by...
). Space-filling trees have interesting parallels in nature, including fluid distribution systems, vascular networks, and fractal
Fractal
A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
plant growth, and many interesting connections to L-system
L-system
An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar, most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms...
s 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 convergesLimit of a sequence
The limit of a sequence is, intuitively, the unique number or point L such that the terms of the sequence become arbitrarily close to L for "large" values of n...
to it.
The term "space-filling tree" in this sense was created in a 2009 tech report that defines "space-filling" and "tree" differently than their traditional definitions in mathematics. As explained in the space-filling curve
Space-filling curve
In mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square...
article, in 1890, Peano found the first space-filling curve, and by Jordan's
Camille Jordan
Marie Ennemond Camille Jordan was a French mathematician, known both for his foundational work in group theory and for his influential Cours d'analyse. He was born in Lyon and educated at the École polytechnique...
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
Space-filling curve
In mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square...
).
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 in 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 everywhereDense set
In topology and related areas of mathematics, a subset A of a topological space X is called dense if any point x in X belongs to A or is a limit point of A...
in the unit square.
Examples
The simplest example of a space-filling tree is one that fills a squareSquare (geometry)
In geometry, a square is a regular quadrilateral. This means that it has four equal sides and four equal angles...
planar region. The images illustrate the construction for the planar region
. 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
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....
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
and hypercubes in .A similar sequence of iterations used for the square
Square (geometry)
In geometry, a square is a regular quadrilateral. This means that it has four equal sides and four equal angles...
space-filling tree can be used for hypercubes. The third iteration of such a space-filling tree in
is illustrated below:See also
- H treeH treeThe H tree is a family of fractal sets whose Hausdorff dimension is equal to 2...
- Space-filling curveSpace-filling curveIn mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square...
- Rapidly-exploring random treeRapidly-exploring random treeA Rapidly-exploring random tree is a data structure and algorithm designed for efficiently searching nonconvex, high-dimensional search spaces. The tree is constructed in such a way that any sample in the space is added by connecting it to the closest sample already in the tree.RRTs, developed by...
(RRTs)