H木
From Wikipedia, the free encyclopedia
構成
性質
H木は自己相似図形(フラクタル図形)であり、そのハウスドルフ次元は2である[2]。
矩形(白銀比の長方形)内の任意の点に対し、十分近いH木上の点が存在する。しかし、全ての点が「含まれる」わけではなく、例えば1ステップ目の線分に対する垂直二等分線はH木に含まれない。
応用
集積回路の設計において、H木は木のノード数に比例する面積を使用する、完全二分木のレイアウトとして用いられる[3]。また、H木の形は長方形内に効率的にグラフを描画可能であり[4]、巡回セールスマン問題の距離の自乗和が大きくなる点の集合としても用いられる[5]。
H木は全てのノードまでの距離が等しいため、中央に発振子を置き、葉ノードの位置に素子を置くことで、クロックの伝播遅延を揃えることができる[6]。そして、VLSIマルチプロセッサの相互接続ネットワークとしても用いられる[7]。同様の理由で、H木は各マイクロストリップアンテナが受信した信号の伝播遅延を揃えることができるため、マイクロストリップアンテナアレイに用いられる。
これまで述べたような2次元平面上のH木は、H木の平面に対して垂直な方向に線分を加えるように変更することで、3次元構造へと一般化することが可能である[8]。この処理により構成される3次元H木は、ハウスドルフ次元が3である。2次元H木と3次元H木は、フォトニック結晶やメタマテリアルにおいて artificial electromagnetic atoms を構成することが知られており、マイクロ波工学において潜在的な用途を有する可能性がある。
関連する集合
H木はフラクタルキャノピーの1つであり、隣接する線分間の角度は常に180度である。矩形内の任意の点に対して十分近づくという性質を持つため、「曲線」ではないが、空間充填曲線に似ている。
位相幾何学的には、H木にはデンドロイドと同様の性質があるといえる。しかし、デンドロイドは閉集合である必要があるため、閉集合ではないH木はデンドロイドではない。
マンデルブロ木は、より自然な見た目を生成するために、H木の位置から僅かにずれた位置に、線分の代わりに長方形を使用するフラクタル図形である。長方形同士が重ならないようにするために、スケールを1/√2より小さくする必要がある[9]。
