H樹

在分形幾何中，H樹（英語：H tree）是一種分形樹結構，由互相垂直的線段構成，其中任意一條線段的長度都是次一級線段的 ${\sqrt {2}}$ 倍。它因類似於字母「H」的重複圖案而得名。它的豪斯多夫維數為2，能任意接近矩形中的每一點。其應用包括超大規模集成電路設計和微波工程。

構造

H樹可從任意長度的線段開始構造，首先在該線段的兩個端點作出兩條垂線，如此反覆，同時將每級繪製的線段長度縮短 ${\sqrt {2}}$ 倍。^[1]

另一種生成相同分形集的方法是從一個邊長比為1: ${\sqrt {2}}$ 的矩形（稱為「銀矩形」）開始，將其重複平分為兩個較小的銀矩形，每級中用線段連接兩個較小矩形的幾何中心。可以在其他任意形狀的矩形中進行類似的過程，但在銀矩形中，每級線段長度以 ${\sqrt {2}}$ 倍均勻減小，而對於其他矩形，長度會以奇偶交替的方式以不同的倍率減小。

性質

H樹是自相似的分形；其豪斯多夫維數為2。^[2]

H樹的節點能任意接近矩形中的每一點（劃分出的矩形的質心對於用於構建的原矩形也一樣）。然而，其並不包括矩形內的所有點，如初始線段的垂直平分線。

應用

在超大規模集成電路的設計中，H樹可以作為完全二叉樹布局，其總使用面積與樹節點的數目成正比^[3]。此外在圖表繪製中，H樹布局能節省空間^[4]，可作為點集結構的一部分^[5]。

它通常用於時鐘分配網絡，以將時鐘信號路由至芯片各處，而傳播延遲相同^[6]，還用作VLSI多處理器中的互連網絡^[7]。出於同樣的原因，H樹還用於微帶天線陣列的排布上，以使每個獨立的微帶天線獲得的無線信號有相等的傳播延遲。

平面H樹可以經由在H樹平面垂直方向添加線段而推廣到三維結構^[8]。所得三維H樹的豪斯多夫維數為3。已經發現光子晶體和超材料中的人造電磁原子構成了平面及立體H樹的結構，還可能在微波工程中有潛在應用^[8]。

有關分形集

H樹是分形冠的一個例子，其中相鄰線段所成角始終為180度。就其能任意接近邊界矩形中每個點的性質而言，它又像是一條空間填充曲線，雖然它本身並不是一條曲線。

拓撲學上，H樹有類似於樹枝狀的性質。但它並不是枝狀的：枝狀必須為閉集，而H樹未封閉（其閉包為整個矩形）。

曼德爾布羅樹是一個與之密切相關的分形，它使用矩形而不是線段，且與H樹的位置略有偏差，以使外觀更自然。為了抵償部件寬度的增加，避免自重疊，每級部件的縮小倍數必須比 ${\sqrt {2}}$ 稍大。^[9]

注

^ H-Fractal （頁面存檔備份，存於網際網路檔案館）, Sándor Kabai, The Wolfram Demonstrations Project.
^ Kaloshin & Saprykina (2012).
^ Leiserson (1980).
^ Nguyen & Huang (2002).
^ Bern & Eppstein (1993).
^ Ullman (1984); Burkis (1991).
^ Browning (1980). See especially Figure 1.1.5, page 15.
^ ^8.0 ^8.1 Hou et al. (2008); Wen et al. (2002).
^ Weisstein, Eric W. (編). Mandelbrot Tree. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.

參考

Bern, Marshall; Eppstein, David, Worst-case bounds for subadditive geometric graphs, Proc. 9th Annual Symposium on Computational Geometry (PDF), Association for Computing Machinery: 183–188, 1993 [2014-12-28], doi:10.1145/160985.161018, （原始內容存檔 (PDF)於2015-07-03） .
Browning, Sally A., The Tree Machine: A Highly Concurrent Computing Environment, Ph.D. thesis, California Institute of Technology, 1980 [2014-12-28], （原始內容存檔於2012-07-16） .
Burkis, J., Clock tree synthesis for high performance ASICs, IEEE International Conference on ASIC: 9.8.1–9.8.4, 1991, doi:10.1109/ASIC.1991.242921 .
Hou, Bo; Xie, Hang; Wen, Weijia; Sheng, Ping, Three-dimensional metallic fractals and their photonic crystal characteristics, Physical Review B, 2008, 77: 125113, doi:10.1103/PhysRevB.77.125113 .
Kaloshin, Vadim; Saprykina, Maria, An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension, Communications in Mathematical Physics, 2012, 315 (3): 643–697, MR 2981810, doi:10.1007/s00220-012-1532-x .
Leiserson, Charles E., Area-efficient graph layouts, 21st Annual Symposium on Foundations of Computer Science (FOCS 1980): 270–281, 1980, doi:10.1109/SFCS.1980.13 .
Nguyen, Quang Vinh; Huang, Mao Lin, A space-optimized tree visualization, IEEE Symposium on Information Visualization: 85–92, 2002, doi:10.1109/INFVIS.2002.1173152 .
Ullman, Jeffrey D., Computational Aspects of VSLI, Computer Science Press, 1984 .
Wen, Weijia; Zhou, Lei; Li, Jensen; Ge, Weikun; Chan, C. T.; Sheng, Ping, Subwavelength photonic band gaps from planar fractals 89, Physical Review Letters: 223901, 2002, doi:10.1103/PhysRevLett.89.223901 .

擴展閱讀

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

外部連結

[1] H-Fractal （頁面存檔備份，存於網際網路檔案館）, Sándor Kabai, The Wolfram Demonstrations Project.

[FOOTNOTEKaloshinSaprykina2012-2] Kaloshin & Saprykina (2012).

[FOOTNOTELeiserson1980-3] Leiserson (1980).

[FOOTNOTENguyenHuang2002-4] Nguyen & Huang (2002).

[FOOTNOTEBernEppstein1993-5] Bern & Eppstein (1993).

[6] Ullman (1984); Burkis (1991).

[7] Browning (1980). See especially Figure 1.1.5, page 15.

[Hou&Wen-8] 8.0 ^8.1 Hou et al. (2008); Wen et al. (2002).

[9] Weisstein, Eric W. (編). Mandelbrot Tree. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]