en>Tomruen: /* = Related polytopes */

2013-10-23T20:18:38Z

= Related polytopes

New page

{{Notability|date=June 2011}}

'''Space-ﬁlling trees''' are geometric constructions that are analogous to [[space-filling curve]]s,<ref>Sagan, H. and J. Holbrook: "Space-filling curves", Springer-Verlag, New York, 1994</ref> but have a branching, tree-like structure and are rooted. A space-ﬁlling tree is deﬁned by an incremental process that results in a tree for which every point in the space has a ﬁnite-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.
<ref>Kuffner, J.J. and S.M. LaValle: ''Space-filling Trees'', The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.</ref> <ref>Kuffner, J.J.; LaValle, S.M.; “Space-filling trees: A new perspective on incremental search for motion planning,” Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on , vol., no., pp.2199-2206, 25-30 Sept. 2011</ref> 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 method|Monte-Carlo]] variants (see [[Rapidly exploring random tree]]). Space-filling trees have interesting parallels in nature, including [[ﬂuid distribution system]]s, [[vascular network]]s, and [[fractal]] plant growth, and many interesting connections to [[L-system]]s in computer science.

==Definition==

A space-filling tree is defined by an iterative process whereby a single point in a [[continuity (topology)|continuous]] space is connected via a continuous path to every other point in the space by a path of [[Wikt:finite|finite]] length, and for every point in the space, there is at least one path that [[Limit of a sequence|converges]] to it.

The term "space-filling tree" in this sense was created in a 2009 tech report <ref>Kuffner, J.J. and S.M. LaValle: ''Space-filling Trees'', The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.</ref> 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 [[Camille Jordan|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 <math>T_{square}</math> as a "sequence of trees", then states "<math>T_{square}</math> 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 set|dense everywhere]] in the unit square.

==Examples==
The simplest example of a space-filling tree is one that fills a [[square (geometry)|square]] planar region. The images illustrate the construction for the planar region <math>[0,1]^2 \subset \Re^2</math>. At each iteration, additional branches are added to the existing trees.

<gallery perrow="3">
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)
</gallery>

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.

<gallery widths="500px" heights = "150px">
Image:Space_Filling_Tree_Tri_iter_1_2_3.png|Subdivision scheme for the first three iterations of the triangle space-filling tree
</gallery>

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

<gallery perrow="3">
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)
</gallery>

Space-filling trees can also be constructed in higher dimensions. The simplest examples are [[Cubes]] in <math>\Re^3</math> and [[hypercubes]] in <math>\Re^n</math>.
A similar sequence of iterations used for the [[square (geometry)|square]] space-filling tree can be used for hypercubes. The third iteration of such a space-filling tree in <math>\Re^3</math> is illustrated below:

<gallery widths="300px" heights="300px">
Image:Space_Filling_Tree_Cube3.png|Cube space-filling tree (Iteration 3)
</gallery>

==See also {{anchor|see also}}==
:*[[H tree]]
:*[[Space-filling curve]]
:*[[Rapidly exploring random tree]] (RRTs)

==References {{anchor|Notes|References|Notes or references}}==
<references/>

[[Category:Fractals]]

Rectified 5-cubes - Revision history

en>Tomruen: /* = Related polytopes */