Los árboles que llenan el espacio son construcciones geométricas que son análogas a las curvas que llenan el espacio , [1] pero tienen una estructura ramificada, similar a un árbol y están enraizadas. 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 llegar rápidamente a 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, auto-similar , pero pueden generalizarse a no regulares e incluso aleatorizados / Monte-Carlovariantes (consulte Exploración rápida de árboles aleatorios ). Los árboles que llenan el espacio tienen interesantes paralelos en la naturaleza, incluidos los sistemas de distribución de fluidos , las redes vasculares y el crecimiento de plantas fractales , y muchas conexiones interesantes con los sistemas L en la informática.
Definición
Un árbol que llena el espacio se define mediante un proceso iterativo mediante el cual un solo punto en un espacio continuo está conectado a través de una ruta continua a cualquier otro punto en el espacio por una ruta de longitud finita , y para cada punto en el espacio, hay un al menos un camino que converge hacia él.
El término "árbol que llena el espacio" en este sentido se creó en un informe técnico de 2009 [4] que define "árbol que llena el espacio" y "árbol" de manera diferente a sus definiciones tradicionales en matemáticas. Como se explica en el artículo de la curva de llenado de espacio , en 1890, Peano encontró la primera curva de llenado de espacio y, según la definición de Jordan de 1887, que ahora es estándar, una curva es una función única, no una secuencia de funciones. La curva es "relleno de espacio" porque es "una curva cuyo rango contiene la unidad cuadrada bidimensional completa" (como se explica en la primera oración de la curva de relleno de espacio ).
Por el contrario, un árbol que llena el espacio, como se define en el informe técnico, no es un árbol único. Es solo una secuencia de árboles. El documento dice que "un árbol que llena el espacio se define en realidad como una secuencia infinita de árboles". Se define como una "secuencia de árboles", luego dice "es un árbol que llena el espacio ". No llena el espacio en el sentido estándar de incluir todo el cuadrado de la unidad bidimensional. En cambio, el documento lo define como árboles en la secuencia que se acercan arbitrariamente a cada punto. Dice" Una secuencia de árbol T se llama 'relleno de espacio' en un espacio X si para cada x ∈ X , existe una ruta en el árbol que comienza en la raíz y converge ax ". El término estándar para este concepto es que incluye un conjunto de puntos que es denso en todas partes del cuadrado unitario.
Ejemplos de
El ejemplo más simple de un árbol que llena el espacio es uno que llena una región plana cuadrada . Las imágenes ilustran la construcción de la región plana.. En cada iteración, se agregan ramas adicionales a los árboles existentes.
Árbol de relleno de espacio cuadrado (iteración 1)
Árbol de relleno de espacio cuadrado (iteración 2)
Árbol de relleno de espacio cuadrado (iteración 3)
Árbol de relleno de espacio cuadrado (iteración 4)
Árbol de relleno de espacio cuadrado (iteración 5)
Árbol de relleno de espacio cuadrado (iteración 6)
Los árboles que llenan el espacio también se pueden definir para una variedad de otras formas y volúmenes. A continuación se muestra el esquema de subdivisión utilizado para definir un relleno de espacio para una región triangular. En cada iteración, se agregan ramas adicionales a los árboles existentes que conectan 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 de relleno de espacio triangular
Las primeras seis iteraciones del árbol que llena el espacio del triángulo se ilustran a continuación:
Árbol que llena el espacio del triángulo (iteración 1)
Árbol que llena el espacio del triángulo (iteración 2)
Árbol que llena el espacio del triángulo (iteración 3)
Árbol que llena el espacio del triángulo (iteración 4)
Árbol que llena el espacio del triángulo (iteración 5)
Árbol que llena el espacio del triángulo (iteración 6)
Los árboles que llenan el espacio también se pueden construir en dimensiones más altas. Los ejemplos más simples son cubos ene hipercubos en. Una secuencia similar de iteraciones utilizada para el árbol de relleno de espacio cuadrado se puede utilizar para hipercubos. La tercera iteración de tal árbol que llena el espacio en se ilustra a continuación:
Árbol que llena el espacio del cubo (iteración 3)
Ver también
Referencias
- ^ Sagan, H. y J. Holbrook: "Curvas que llenan el espacio", Springer-Verlag, Nueva York, 1994
- ^ Kuffner, JJ y SM LaValle: Árboles que llenan el espacio , The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.
- ^ Kuffner, JJ; LaValle, SM; “Árboles que llenan el espacio: una nueva perspectiva sobre la búsqueda incremental para la planificación del movimiento”, Intelligent Robots and Systems (IROS), 2011 IEEE / RSJ International Conference on, vol., No., Pp.2199-2206, 25-30 de septiembre. 2011
- ^ Kuffner, JJ y SM LaValle: Árboles que llenan el espacio , The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.