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.

Les dix premiers niveaux d'un arbre en H

Construction

Un 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, rectange 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

Un 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

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
Carré en T
Branches carrées reliées par le nombre d'or.
Branches carrées reliées par 1/2.

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
  1. H-Fractal, Sándor Kabai, Wolfram Demonstrations Project.
  2. Kaloshin et Saprykina (2012).
  3. Leiserson (1980).
  4. Nguyen et Huang (2002).
  5. Bern et Eppstein (1993).
  6. Hou et al. 2008; Wen et al. 2002.

Références
  • Portail des mathématiques
  • Portail de l'informatique théorique

Liens externes
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.