Space-filling tree

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.

  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