Space-filling trees and Space-filling tree: Difference between pages
No edit summary |
migrated content of plural page to new singular page |
(No difference)
| |
Revision as of 22:26, 9 February 2010
 | This article or section is in a state of significant expansion or restructuring. You are welcome to assist in its construction by editing it as well. If this article or section has not been edited in several days, please remove this template. If you are the editor who added this template and you are actively editing, please be sure to replace this template with {{in use}} during the active editing session. Click on the link for template parameters to use.
This article was last edited by Jkuff (talk | contribs) 14 years ago. (Update timer) |
Space-filling trees are geometric constructions that are analogous to space-filling curves, but have a branching, tree-like structure and are rooted[1]. 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. 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.
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.
![{\displaystyle [0,1]^{2}\subset \Re ^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fe9237e3963a63106be1c27543d8827fc3370d6)
-
Square space-filling tree (Iteration 1)
-
Square space-filling tree (Iteration 2)
-
Square space-filling tree (Iteration 3)
-
Square space-filling tree (Iteration 4)
-
Square space-filling tree (Iteration 5)
-
Square space-filling tree (Iteration 6)
See also
References
- ^ Kuffner, J.J. and S.M. LaValle: Space-filling Trees, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.