Árbol que llena el espacio

Los árboles que llenan el espacio son construcciones geométricas análogas a las curvas que llenan el espacio , ^{[ 1 ]} pero tienen una estructura ramificada, similar a un árbol, y están enraizados. Un árbol que llena el espacio se define mediante un proceso incremental que da como resultado un árbol para el cual cada punto en el espacio tiene un camino de longitud finita que converge hacia él. A diferencia de las curvas que llenan el espacio , los caminos individuales en el árbol son cortos, lo que permite alcanzar rápidamente cualquier parte del espacio desde la raíz. ^{[ 2 ] [ 3 ]} Los ejemplos más simples de árboles que llenan el espacio tienen una estructura fractal regular y autosimilar , pero pueden generalizarse a variantes no regulares e incluso aleatorias / Monte Carlo (ver Exploración rápida de árboles aleatorios ). Los árboles que llenan el espacio tienen paralelismos interesantes en la naturaleza, incluyendo sistemas de distribución de fluidos , redes vasculares y crecimiento fractal de plantas, y muchas conexiones interesantes con los sistemas L en ciencias de la computación .

Un árbol que llena el espacio se define mediante un proceso iterativo en el que un único punto en un espacio continuo se conecta a través de un camino continuo a todos los demás puntos del espacio mediante un camino de longitud finita , y para cada punto del espacio, hay al menos un camino que converge hacia él.

El concepto de "árbol que llena el espacio" en este sentido se describió en el Capítulo 15 del influyente libro de Mandelbrot , La geometría fractal de la naturaleza (1982). ^{[ 4 ]} El concepto se hizo más riguroso y se le dio el nombre de "árbol que llena el espacio" en un informe técnico de 2009 ^{[ 5 ]} que define "llena el espacio" y "árbol" de manera diferente a sus definiciones tradicionales en matemáticas. Como se explica en el artículo sobre la curva que llena el espacio , en 1890, Peano encontró la primera curva que llena el espacio, y según la definición de Jordan de 1887, que ahora es estándar, una curva es una sola función, no una secuencia de funciones. La curva es "que llena el espacio" porque es "una curva cuyo rango contiene todo el cuadrado unitario bidimensional " (como se explica en la primera oración de la curva que llena el espacio ).

En cambio, un árbol que llena el espacio, tal como se define en el informe técnico, no es un solo árbol. Es solo una secuencia de árboles. El documento dice: "Un árbol que llena el espacio se define en realidad como una secuencia infinita de árboles". Define${\displaystyle T_{\text{cuadrado}}}$como una "secuencia de árboles", luego afirma:${\displaystyle T_{\text{cuadrado}}}$es un árbol que llena el espacio". No lo es en el sentido estándar de incluir todo el cuadrado unitario bidimensional. En cambio, el artículo lo define como una secuencia de árboles que se aproximan arbitrariamente a cada punto. Afirma: "Una secuencia de árboles T se denomina 'llena el espacio' en un espacio X si para cada x ∈ X , existe un camino en el árbol que comienza en la raíz y converge a x ". El término estándar para este concepto es que incluye un conjunto de puntos que es denso en todo el cuadrado unitario.   

El ejemplo más sencillo de un árbol que llena el espacio es aquel que llena una región plana cuadrada . Las imágenes ilustran la construcción para la región plana.${\displaystyle [0,1]^{2}\subset \mathbb {R} ^{2}}$En cada iteración, se añaden ramas adicionales a los árboles existentes.

• 
  Árbol cuadrado que llena el espacio (Iteración 1)
• 
  Árbol cuadrado que llena el espacio (Iteración 2)
• 
  Árbol cuadrado que llena el espacio (Iteración 3)
• 
  Árbol cuadrado que llena el espacio (Iteración 4)
• 
  Árbol cuadrado que llena el espacio (Iteración 5)
• 
  Árbol cuadrado que llena el espacio (Iteración 6)

También se pueden definir árboles que rellenen el espacio para diversas formas y volúmenes. A continuación se muestra el esquema de subdivisión utilizado para definir un árbol que rellene el espacio en una región triangular. En cada iteración, se añaden ramas adicionales a los árboles existentes, conectando el centro de cada triángulo con los centros de los cuatro subtriángulos.

• 
  Esquema de subdivisión para las tres primeras iteraciones del árbol triangular que llena el espacio.

Las primeras seis iteraciones del árbol triangular que llena el espacio se ilustran a continuación:

• 
  Árbol triangular que llena el espacio (Iteración 1)
• 
  Árbol triangular que llena el espacio (Iteración 2)
• 
  Árbol triangular que llena el espacio (Iteración 3)
• 
  Árbol triangular que llena el espacio (Iteración 4)
• 
  Árbol triangular que llena el espacio (Iteración 5)
• 
  Árbol triangular que llena el espacio (Iteración 6)

Los árboles que llenan el espacio también se pueden construir en dimensiones superiores. Los ejemplos más simples son los cubos en${\displaystyle \mathbb {R} ^{3}}$y los hipercubos en${\displaystyle \mathbb {R} ^{n}}$. Una secuencia de iteraciones similar a la utilizada para el árbol cuadrado que llena el espacio se puede utilizar para hipercubos. La tercera iteración de dicho árbol que llena el espacio en${\displaystyle \mathbb {R} ^{3}}$Se ilustra a continuación:

• 
  Árbol cúbico que llena el espacio (Iteración 3)

• Árbol H
• Curva que llena el espacio
• Árboles aleatorios de exploración rápida (RRT)
• Particionamiento binario del espacio