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

H樹的前十層

構造

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

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

性質

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樹的位置略有偏差,以使外觀更自然。為了抵償部件寬度的增加,避免自重疊,每級部件的縮小倍數必須比 稍大。[9]

參考

擴充閱讀

  • 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 .

外部連結