H-stablo

Prvih deset nivoa H-stabla

U fraktalnoj geometriji, H-stablo je fraktalna struktura stabla konstruisanog od normalnih linijskih segmenata, gde je svaki prethodni za kvadratni koren od 2 manji od sledećeg, većeg segmenta. Zove se upravo ovim imenom zbog toga što njegov ponavljajući šablon podseća na latinično slovo "H". Ima Hausdorfovu dimenziju 2, i nalazi se proizvoljno blizu svakoj tački pravougaonika. Njegove aplikacije uključuju VLSI dizajn i inženjering mikrotalasa.

Konstrukcija

H-stablo se može konstruisati tako što se polazi od linijskog segmenta proizvoljne dužine, crtajući dva kraća segmenta pod pravim uglom u odnosu na početni segment kroz njegove krajnje tačke, i nastavljajući u istom maniru, smanjujući dužine linijskih segmenata u svakom sledećem koraku za √2.

Alternativni proces koji generiše isti fraktalni set vrši se tako što se počne sa pravougaonikom čije su stranice u razmeri 1:√2, koji je poznat i kao "srebrni pravougaonik", i koji se dalje deli na dva manja srebrna pravougaonika, dok se u svakom sledećem koraku linijskim segmentom povezuju dva težišta dva manja pravougaonika. Sličan proces se može izvesti i sa pravougaonicima bilo koje razmere stranica, međutim samo srebrni pravougaonik vodi ravnomernom smanjenju linijskog segmenta u svakom koraku za vrednost √2 dok se kod ostalih pravougaonika dužina smanjuje za različite slučajne vrednosti.

Osobine

H-stablo je sebi sličan fraktal; njegova Hausdorfova dimenzija jednaka je 2.

Tačke H-stabla nalaze se proizvoljno blizu svakoj tački pravougaonika (isto kao u slučaju početnog pravougaonika u konstrukciji sa težištima manjih podeljenih pravougaonika). Međutim, nisu uključene sve tačke pravougaonika; na primer centar početnog linijskog segmenta nije uključen.

Aplikacije

U VLSI dizajnu, H-stablo može da se koristi kao plan za uredjeno binarno stablo koristeći celu oblast koja je proporcionalna broju čvorova stabla. Dodatno, H-stablo formira prostorno efikasan plan za stabla u grafičkom crtanju, i veliki je deo konstrukcije sklopa tačaka koji služi za rešavanje problema trgovačkog putnika.

Često se koristi kao sinhrona mreža za slanje signala časovnika do svih delova čipa sa jednakim kašnjenjem do svakog dela, a takođe se koristilo i kao interkonekciona mreža za VLSI multiprocesore. Iz istog razloga, H-stablo se koristi u nizu mikrostrip antena da bi se preneo radio signal do svake mikrostrip antene pojedinačno sa jednakim kašnjenjem.

Matično H-stablo može biti generisano u trodimenzionalnu strukturu dodajući linijske segmente u pravcu prenosa u planu H-stabla. Rezultirajuće trodimenzionalno H-stablo ima Hausdorfovu dimenziju jednaku 3. Otkriveno je da matično H-stablo i njegova trodimenziona verzija konstruišu veštačke elektromagnetne atome u fotoničkim kristalima i metamaterijalima i da potencijalno mogu imati primenu u inženjeringu mikrotalasa.

Srodni sklopovi

H-stablo je primer fraktalne mreže u kojoj je ugao između dva susedna linijska segmenta uvek 180 stepeni. Zbog svog svojstva da se nađe proizvoljno blizu svakoj tački svog graničnog pravougaonika takođe podseća na beskonačno gustu krivu, iako samo po sebi nije kriva.

Topološki, H-stablo ima osobine slične dendritu. Međutim, ono nije dendrit: dendriti moraju biti zatvoreni sklopovi, a H-stablo nije zatvoreno (njegovo zatvaranje predstavlja čitav pravougaonik).

Mandelbrot-stablo je veoma blisko povezan fraktal koji koristi pravougaonike umesto linijskih segmenata, u cilju stvaranja prirodnijeg izgleda. Kao kompenzaciju za veću širinu svojih komponenti i da bi se izbeglo preklapanje, faktor vrednosti za koju se smanjuje veličina komponenti na svakom nivou mora biti malo veća od √2.

Literatura

• Bern, Marshall; Eppstein, David (1993), „Worst-case bounds for subadditive geometric graphs”, Proc. 9th Annual Symposium on Computational Geometry (PDF), Association for Computing Machinery, стр. 183—188, doi:10.1145/160985.161018 .
• Browning, Sally A. (1980), The Tree Machine: A Highly Concurrent Computing Environment, Ph.D. thesis, California Institute of Technology, Архивирано из оригинала 16. 07. 2012. г., Приступљено 31. 05. 2015 .
• Burkis, J. (1991), „Clock tree synthesis for high performance ASICs”, IEEE International Conference on ASIC, стр. 9.8.1—9.8.4, doi:10.1109/ASIC.1991.242921 .
• Hou, Bo; Xie, Hang; Wen, Weijia; Sheng, Ping (2008), „Three-dimensional metallic fractals and their photonic crystal characteristics”, Physical Review B, 77: 125113, doi:10.1103/PhysRevB.77.125113 .
• Kaloshin, Vadim; Saprykina, Maria (2012), „An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension”, Communications in Mathematical Physics, 315 (3): 643—697, MR 2981810, doi:10.1007/s00220-012-1532-x .
• Leiserson, Charles E. (1980), „Area-efficient graph layouts”, 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), стр. 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, стр. 85—92, doi:10.1109/INFVIS.2002.1173152 .
• Ullman, Jeffrey D. (1984), Computational Aspects of VSLI, Computer Science Press .
• Wen, Weijia; Zhou, Lei; Li, Jensen; Ge, Weikun; Chan, C. T.; Sheng, Ping (2002), Subwavelength photonic band gaps from planar fractals, 89, Physical Review Letters, стр. 223901, doi:10.1103/PhysRevLett.89.223901 .

Vidi još

• Kabai, S. (2002), Mathematical Graphics I: Lessons in Computer Graphics Using Mathematica, Püspökladány, Hungary: Uniconstant, стр. 231 .
• Lauwerier, H. (1991), Fractals: Endlessly Repeated Geometric Figures, Princeton, NJ: Princeton University Press, стр. 1—2 .

Spoljašnje veze

• Famous Fractals - H-fractal
• Weisstein, Eric W. „H-Fractal”. MathWorld. 
• Moving H-fractal (including Java Applet)