En geometría fractal , el árbol H , o ramificación en T , es una estructura de árbol fractal construida a partir de segmentos de líneas perpendiculares , cada uno más pequeño por un factor de la raíz cuadrada de 2 del siguiente segmento adyacente más grande. Se llama así porque su patrón repetido se asemeja a la letra "H". Tiene una dimensión de Hausdorff 2 y se acerca arbitrariamente a cada punto de un rectángulo . Sus aplicaciones incluyen diseño VLSI e ingeniería de microondas.
Construcción
Se puede construir un árbol H comenzando con un segmento de línea de longitud arbitraria, dibujando dos segmentos más cortos en ángulo recto con el primero a través de sus extremos, y continuando en la misma línea, reduciendo (dividiendo) la longitud de los segmentos de línea dibujados en cada uno. etapa por √ 2 . [1]
Un proceso alternativo que genera el mismo conjunto fractal es comenzar con un rectángulo con lados en la proporción 1: √ 2 , conocido como " rectángulo plateado ", y dividirlo repetidamente en dos rectángulos plateados más pequeños, en cada etapa conectando los dos centroides. de los dos rectángulos más pequeños por un segmento de línea. Se puede realizar un proceso similar con rectángulos de cualquier otra forma, pero el rectángulo plateado hace que el tamaño del segmento de línea disminuya uniformemente en un factor √ 2 en cada paso, mientras que para otros rectángulos la longitud disminuirá en diferentes factores a niveles pares e impares de la construcción recursiva.
Propiedades
El árbol H es un fractal auto-similar ; su dimensión de Hausdorff es igual a 2. [2]
Los puntos del árbol H se acercan arbitrariamente a cada punto de un rectángulo (lo mismo que el rectángulo inicial en la construcción por centroides de rectángulos subdivididos). Sin embargo, no incluye todos los puntos del rectángulo; por ejemplo, no se incluye la bisectriz perpendicular del segmento de línea inicial.
Aplicaciones
En el diseño de VLSI , el árbol H puede usarse como diseño para un árbol binario completo usando un área total que es proporcional al número de nodos del árbol. [3] Además, el árbol H forma un diseño de espacio eficiente para árboles en el dibujo gráfico , [4] y como parte de la construcción de un conjunto de puntos para el cual la suma de las longitudes de los bordes al cuadrado del recorrido del vendedor ambulante es grande. [5]
Se utiliza comúnmente como una red de distribución de reloj para enrutar señales de temporización a todas las partes de un chip con retrasos de propagación iguales a cada parte, [6] y también se ha utilizado como una red de interconexión para multiprocesadores VLSI. [7] Por la misma razón, el árbol H se utiliza en arreglos de antenas de microbanda para llevar la señal de radio a cada antena de microbanda individual con el mismo retardo de propagación.
El árbol H plano se puede generalizar a la estructura tridimensional agregando segmentos de línea en la dirección perpendicular al plano del árbol H. [8] El árbol H tridimensional resultante tiene una dimensión de Hausdorff igual a 3. Se ha descubierto que el árbol H plano y su versión tridimensional constituyen átomos electromagnéticos artificiales en cristales fotónicos y metamateriales y podrían tener aplicaciones potenciales en la ingeniería de microondas. [8]
Conjuntos relacionados
El árbol H es un ejemplo de un dosel fractal , en el que el ángulo entre los segmentos de línea vecinos es siempre de 180 grados. En su propiedad de acercarse arbitrariamente a cada punto de su rectángulo delimitador, también se asemeja a una curva que llena el espacio , aunque no es en sí misma una curva.
Topológicamente , un árbol H tiene propiedades similares a las de un dendroide . Sin embargo, no son dendroides: los dendroides deben ser conjuntos cerrados y los árboles H no están cerrados (su cierre es el rectángulo completo).
El árbol de Mandelbrot es un fractal muy relacionado que utiliza rectángulos en lugar de segmentos de línea, ligeramente desplazados de las posiciones del árbol H, para producir una apariencia más naturalista. Para compensar el aumento de ancho de sus componentes y evitar la superposición automática, el factor de escala por el cual se reduce el tamaño de los componentes en cada nivel debe ser ligeramente mayor que √ 2 . [9]
Ver también
- Árbol en T
Notas
- ^ H-Fractal , Sándor Kabai, El proyecto de demostraciones de Wolfram .
- ^ Kaloshin y Saprykina (2012) .
- ^ Leiserson (1980) .
- ^ Nguyen y Huang (2002) .
- ^ Bern y Eppstein (1993) .
- ^ Ullman (1984) ; Burkis (1991) .
- ^ Browning (1980) . Ver especialmente la Figura 1.1.5, página 15.
- ^ a b Hou y col. (2008) ; Wen y col. (2002) .
- ^ Weisstein, Eric W. "Árbol de Mandelbrot" . MathWorld .
Referencias
- Berna, Marshall; Eppstein, David (1993), "Límites del peor caso para gráficos geométricos subaditivos", Proc. Noveno Simposio Anual sobre Geometría Computacional (PDF) , Association for Computing Machinery , págs. 183–188, doi : 10.1145 / 160985.161018.
- Browning, Sally A. (1980), The Tree Machine: Un entorno informático altamente concurrente , Ph.D. tesis, Instituto de Tecnología de California.
- Burkis, J. (1991), "Síntesis de árbol de reloj para ASIC de alto rendimiento", IEEE International Conference on ASIC , págs. 9.8.1–9.8.4, doi : 10.1109 / ASIC.1991.242921.
- Hou, Bo; Xie, cuelgue; Wen, Weijia; Sheng, Ping (2008), "Fractales metálicos tridimensionales y sus características de cristal fotónico" (PDF) , Physical Review B , 77 (12): 125113, doi : 10.1103 / PhysRevB.77.125113.
- Kaloshin, Vadim; Saprykina, Maria (2012), "Un ejemplo de un sistema hamiltoniano casi integrable con una trayectoria densa en un conjunto de dimensión máxima de Hausdorff", Communications in Mathematical Physics , 315 (3): 643–697, doi : 10.1007 / s00220-012 -1532-x , MR 2981810.
- Leiserson, Charles E. (1980), "Diseños de gráficos de área eficiente", 21º Simposio anual sobre los fundamentos de la informática (FOCS 1980) , págs. 270–281, doi : 10.1109 / SFCS.1980.13.
- Nguyen, Quang Vinh; Huang, Mao Lin (2002), "A space-optimized tree visualization", IEEE Symposium on Information Visualization , págs. 85–92, doi : 10.1109 / INFVIS.2002.1173152.
- Ullman, Jeffrey D. (1984), Aspectos computacionales de VSLI , Computer Science Press.
- Wen, Weijia; Zhou, Lei; Li, Jensen; Ge, Weikun; Chan, CT; Sheng, Ping (2002), "Brechas de banda fotónica de sublongitud de onda de fractales planos" (PDF) , Physical Review Letters , 89 (22): 223901, doi : 10.1103 / PhysRevLett.89.223901 , PMID 12485068.
Otras lecturas
- Kabai, S. (2002), Gráficos matemáticos I: Lecciones de gráficos por computadora usando Mathematica , Püspökladány, Hungría: Uniconstant, p. 231.
- Lauwerier, H. (1991), Fractales: Figuras geométricas repetidas sin fin , Princeton, Nueva Jersey: Princeton University Press, págs. 1–2.
enlaces externos
- Fractales famosos - H-fractal
- Weisstein, Eric W. "H-Fractal" . MathWorld .
- Mover el árbol H (incluido el subprograma de Java)