H樹
在分形幾何中，H樹（英語：H tree）是一種分形樹結構，由互相垂直的線段構成，其中任意一條線段的長度都是次一級線段的倍。它因類似於字母「H」的重複圖案而得名。它的郝斯多夫維數為2，能任意接近矩形中的每一點。其應用包括超大規模集成電路設計和微波工程。
構造
[編輯]H樹可從任意長度的線段開始構造，首先在該線段的兩個端點作出兩條垂線，如此反覆，同時將每級繪製的線段長度縮短倍。[1]
另一種生成相同分形集的方法是從一個邊長比為1:的矩形（稱為「銀矩形」）開始，將其重複平分為兩個較小的銀矩形，每級中用線段連接兩個較小矩形的幾何中心。可以在其他任意形狀的矩形中進行類似的過程，但在銀矩形中，每級線段長度以倍均勻減小，而對於其他矩形，長度會以奇偶交替的方式以不同的倍率減小。
性質
[編輯]H樹的節點能任意接近矩形中的每一點（劃分出的矩形的質心對於用於構建的原矩形也一樣）。然而，其並不包括矩形內的所有點，如初始線段的垂直平分線。
應用
[編輯]在超大規模集成電路的設計中，H樹可以作為完全二叉樹佈局，其總使用面積與樹節點的數目成正比[3]。此外在圖表繪製中，H樹佈局能節省空間[4]，可作為點集結構的一部分[5]。
它通常用於時鐘分配網絡，以將時鐘訊號路由至晶片各處，而傳播延遲相同[6]，還用作VLSI多處理器中的互連網絡[7]。出於同樣的原因，H樹還用於微帶天線陣列的排布上，以使每個獨立的微帶天線獲得的無線訊號有相等的傳播延遲。
平面H樹可以經由在H樹平面垂直方向添加線段而推廣到三維結構[8]。所得三維H樹的郝斯多夫維數為3。已經發現光子晶體和超材料中的人造電磁原子構成了平面及立體H樹的結構，還可能在微波工程中有潛在應用[8]。
有關分形集
[編輯]H樹是分形冠的一個例子，其中相鄰線段所成角始終為180度。就其能任意接近邊界矩形中每個點的性質而言，它又像是一條空間填充曲線，雖然它本身並不是一條曲線。
拓撲學上，H樹有類似於樹枝狀的性質。但它並不是枝狀的：枝狀必須為閉集，而H樹未封閉（其閉包為整個矩形）。
曼德爾布羅樹是一個與之密切相關的分形，它使用矩形而不是線段，且與H樹的位置略有偏差，以使外觀更自然。為了抵償部件寬度的增加，避免自重疊，每級部件的縮小倍數必須比稍大。[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.
