Arbre en H
En géométrie fractale, un arbre en H ou arbre H ou une ramification en T est une structure arborescente fractale construite à partir de segments de droites perpendiculaires, chacun plus petit d'un facteur Racine carrée de deux et attaché au segment adjacent plus grand. La structure est appelée ainsi parce que son motif répété la fait ressembler à la lettre « H ». La dimension de Hausdorff de l'arbre est 2, et il est arbitrairement proche de tout point du rectangle. Il a des applications dans la conception des VLSI et dans l'ingénierie des micro-ondes.
Construction
modifierUn arbre en H peut être construit en commençant par un segment de droite de longueur arbitraire, en traçant deux segments plus courts perpendiculairement au premier passant par ses extrémités, et en continuant dans la même façon, en divisant par √2 la longueur des segments de droite tracés à chaque étape[1]. Si, à chaque itération, la longueur est divisée par un rapport supérieur à √2, la courbe résultante ne couvre qu'une partie du rectangle, et a une frontière fractale[2].
Un autre procédé qui engendre le même ensemble fractal consiste à commencer avec un rectangle dont les côtés sont dans le rapport 1 à √2, rectangle connu sous le nom de « rectangle d'argent », et de le couper itérativement en deux rectangles d'argent plus petits, tout en reliant les centroïdes des deux plus petits rectangles par un segment de droite. Un processus similaire peut être effectué avec des rectangles de toute autre forme, mais le rectangle d'argent entraîne une diminution uniforme de la taille du segment de droite d'un facteur √2 à chaque étape, tandis que pour les autres rectangles, la longueur diminue de différents facteurs aux niveaux pairs et impairs de la construction récursive.
Propriétés
modifierUn arbre en H est une fractale autosimilaire ; sa dimension de Hausdorff est égale à 2[2]. C'est une courbe remplissante.
Les points de l'arbre H sont arbitrairement proches des points d'un rectangle (le même rectangle que le rectangle de départ dans la construction par centroïdes de rectangles subdivisés). Cependant, l'arbre n'inclut pas tous les points du rectangle ; par exemple, la bissectrice perpendiculaire au segment de droite initial n'en fait pas partie.
Applications
modifier
Dans la conception des circuits VLSI, l'arbre en H peut être utilisé comme dessin pour un arbre binaire complet utilisant une surface totale proportionnelle au nombre de nœuds de l'arbre[3]. De plus, l'arbre en H forme un tracé efficace en espace pour les arbres dans le tracé de graphes[4], et aussi dans le cadre d'une construction d'un ensemble de points pour lequel la somme des carrés des longueurs d'arêtes de la tournée du voyageur de commerce est grande[5].
L'arbre en H est couramment utilisé comme réseau de distribution d'horloge pour acheminer les signaux de synchronisation vers les parties d'une puce avec des délais de propagation égaux vers chaque pièce, et a également été utilisé comme réseau d'interconnexion pour les multiprocesseurs VLSI. Pour la même raison, l'arbre en H est utilisé dans les réseaux d'antennes micro ruban afin d'acheminer le signal radio vers chaque antenne micro ruban individuelle avec le même délai de propagation.
L'arbre en H planaire peut être généralisé à une structure tridimensionnelle en ajoutant des segments de droite dans la direction perpendiculaire au plan de l'arbre en H.[6] . L'arbre en H tridimensionnel résultant a une dimension de Hausdorff égale à 3. L'arbre en H planaire et sa version tridimensionnelle se sont avérés constituer des atomes électromagnétiques artificiels dans les cristaux photoniques et les métamatériaux et pourraient avoir des applications potentielles dans l'ingénierie des micro-ondes[6].
Ensembles associés
modifier
L'arbre en H est un exemple de canopée fractale, ici l'angle entre les segments de ligne voisins est toujours de 180 degrés. Par sa propriété d'être arbitrairement proche de chaque point de son rectangle cadre, il ressemble également à une courbe remplissante, bien qu'il ne soit pas lui-même une courbe.
Topologiquement, un arbre en H a des propriétés similaires à celles d'un dendroïde (topologie) (en). Cependant, ce ne sont pas des dendroïdes car les dendroïdes sont des ensembles fermés, alors que les arbres en H ne sont pas fermés (leur fermeture est le rectangle entier).
L'arbre de Mandelbrot est une fractale très similaire utilisant des rectangles au lieu de segments de droite, légèrement décalés par rapport aux positions de l'arbre en H, afin de produire une apparence plus naturaliste. Pour compenser la largeur accrue de ses composants et éviter l'auto-chevauchement, le facteur d'échelle par lequel la taille des composants est réduite à chaque niveau doit être légèrement supérieur à √2.
Notes
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « H tree » (voir la liste des auteurs).
Références
modifier- Marshall Bern et David Eppstein, « Worst-case bounds for subadditive geometric graphs », Proc. 9th Annual Symposium on Computational Geometry, Association for Computing Machinery, , p. 183–188 (DOI 10.1145/160985.161018, lire en ligne).
- Sally A. Browning, The Tree Machine: A Highly Concurrent Computing Environment (Thèsse Ph. D.), California Institute of Technology, (lire en ligne).
- J. Burkis, « Clock tree synthesis for high performance ASICs », IEEE International Conference on ASIC, , p. 9.8.1–9.8.4 (DOI 10.1109/ASIC.1991.242921).
- Bo Hou, Hang Xie, Weijia Wen et Ping Sheng, « Three-dimensional metallic fractals and their photonic crystal characteristics », Physical Review B, vol. 77, no 12, , p. 125113 (DOI 10.1103/PhysRevB.77.125113, lire en ligne).
- Vadim Kaloshin et Maria Saprykina, « An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension », Communications in Mathematical Physics, vol. 315, no 3, , p. 643–697 (DOI 10.1007/s00220-012-1532-x, MR 2981810).
- Charles E. Leiserson, « Area-efficient graph layouts », 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), , p. 270–281 (DOI 10.1109/SFCS.1980.13).
- Quang Vinh Nguyen et Mao Lin Huang, « A space-optimized tree visualization », IEEE Symposium on Information Visualization, , p. 85–92 (DOI 10.1109/INFVIS.2002.1173152).
- Jeffrey D. Ullman, Computational Aspects of VSLI, Computer Science Press, .
- Weijia Wen, Lei Zhou, Jensen Li, Weikun Ge, C. T. Chan et Ping Sheng, « Subwavelength photonic band gaps from planar fractals », Physical Review Letters, vol. 89, no 22, , p. 223901 (PMID 12485068, DOI 10.1103/PhysRevLett.89.223901, lire en ligne).
