H木

サムネイル|360x360ピクセル|10ステップ目まで描画したHツリー H木、H treeまたはH-Tree はフラクタル図形の1つであり、直線の両端に、その長さの1/の長さの垂線を追加し続けることによって構成される図形である。繰り返しパターンがアルファベットの "H" に似ているため、H木と呼ばれる。ハウスドルフ次元は2であり、矩形内の任意の点に対し、十分近いH木上の点が存在する。著しい特性として「任意のステップにおいて、中心から端点までの距離がすべて等しい」というものがあり、例えば集積回路におけるクロックの分配などや、マイクロ波工学などへの応用などが代表例として知られている。

構成 H木は、任意の長さの線分を元に、「その線分の両端に垂直な1/の長さの2本の線分を追加する」という処理を繰り返すことで構成できるH-Fractal, Sándor Kabai, The Wolfram Demonstrations Project.。

また、白銀比である1:の長方形から開始し、長辺を2等分し、その重心を直線で結ぶという処理でも構築できる。1: = /2:1であるため、分割された長方形もまた白銀比の長方形である。他の比で表される長方形でも同様の処理は可能であるが、白銀比でない長方形では、奇数ステップと偶数ステップでは重心間の距離の比が一定ではない。

性質 H木は自己相似図形（フラクタル図形）であり、そのハウスドルフ次元は2である。

矩形（白銀比の長方形）内の任意の点に対し、十分近いH木上の点が存在する。しかし、全ての点が「含まれる」わけではなく、例えば1ステップ目の線分に対する垂直二等分線はH木に含まれない。

応用 集積回路の設計において、H木は木のノード数に比例する面積を使用する、完全二分木のレイアウトとして用いられる。また、H木の形は長方形内に効率的にグラフを描画可能であり、巡回セールスマン問題の距離の自乗和が大きくなる点の集合としても用いられる。

H木は全てのノードまでの距離が等しいため、中央に発振子を置き、葉ノードの位置に素子を置くことで、クロックの伝播遅延を揃えることができる; .。そして、VLSIマルチプロセッサの相互接続ネットワークとしても用いられる. See especially Figure 1.1.5, page 15.。同様の理由で、H木は各マイクロストリップアンテナが受信した信号の伝播遅延を揃えることができるため、マイクロストリップアンテナアレイに用いられる。

これまで述べたような2次元平面上のH木は、H木の平面に対して垂直な方向に線分を加えるように変更することで、3次元構造へと一般化することが可能である; .。この処理により構成される3次元H木は、ハウスドルフ次元が3である。2次元H木と3次元H木は、フォトニック結晶やメタマテリアルにおいて artificial electromagnetic atoms を構成することが知られており、マイクロ波工学において潜在的な用途を有する可能性がある。

関連する集合 H木はフラクタルキャノピーの1つであり、隣接する線分間の角度は常に180度である。矩形内の任意の点に対して十分近づくという性質を持つため、「曲線」ではないが、空間充填曲線に似ている。

位相幾何学的には、H木にはデンドロイドと同様の性質があるといえる。しかし、デンドロイドは閉集合である必要があるため、閉集合ではないH木はデンドロイドではない。

マンデルブロ木は、より自然な見た目を生成するために、H木の位置から僅かにずれた位置に、線分の代わりに長方形を使用するフラクタル図形である。長方形同士が重ならないようにするために、スケールを1/√2より小さくする必要がある。

脚注

参考文献

. . . . . . . . .

参考図書 . .

外部リンク Famous Fractals - H-fractal

Moving H-fractal (including Java Applet)