Loading article…
フラクタル幾何学において、Hツリーは、互いに垂直な線分から構成されるフラクタルツリー構造であり、各線分は隣接するより大きな線分よりも√2倍小さくなっています。その繰り返しパターンが文字「H」に似ていることから、この名前が付けられました。ハウスドルフ次元は2であり、長方形内のあらゆる点に任意に近づくことができます。応用例としては、VLSI設計やマイクロ波工学などが挙げられます。
H ツリーは、任意の長さの線分から始めて、最初の線分の端点を通るように、最初の線分に直角な 2 つの短い線分を描き、同じ方法で各段階で描かれた線分の長さを 1 で割って短縮することで構築できます。[ 1 ]この構成の変形として、各反復での長さが以下の比率で乗算されるものも定義できる。しかし、この変種では、結果として得られる形状は境界矩形の一部のみを覆い、フラクタル境界を持つ。[ 2 ]
同じフラクタルセットを生成する別のプロセスは、辺の比率が次の長方形から始めることです。そしてそれを繰り返し2つの小さな銀色の長方形に分割し、各段階で2つの小さな長方形の2つの重心を線分で結びます。同様のプロセスは他の形状の長方形でも実行できますが、長方形は線分のサイズを均一に減少させる各ステップで係数が変化する一方、他の長方形では、再帰的構成の奇数レベルと偶数レベルで長さが異なる係数で減少します。
Hツリーは自己相似フラクタルであり、そのハウスドルフ次元は2である。 [ 2 ]
H ツリーの点は、長方形内のすべての点に任意に近づきます(分割された長方形の重心による構築における開始長方形と同じ)。[ 3 ]その結果、その位相的閉包は長方形全体になります。ただし、長方形のすべての点が含まれるわけではありません。たとえば、最初の線分の垂直二等分線上の点 (この線分の中点以外) は含まれません。
VLSI設計では、Hツリーは、ツリーのノード数に比例した総面積を使用して、完全二分木のレイアウトとして使用できます。 [ 4 ]さらに、Hツリーは、グラフ描画におけるツリーのスペース効率の良いレイアウトを形成し、[ 5 ]巡回セールスマンツアーのエッジ長の二乗の合計が大きい点集合の構築の一部として使用されます。[ 6 ]一般的に、Hツリーは、各部分への伝搬遅延が等しいタイミングで、チップのすべての部分にタイミング信号をルーティングするためのクロック分配ネットワークとして使用され、 [ 7 ]また、VLSIマルチプロセッサの相互接続ネットワークとしても使用されています。[ 8 ]
平面Hツリーは、Hツリー平面に垂直な方向に線分を追加することで、3次元構造に一般化できます。[ 9 ] 結果として得られる3次元Hツリーのハウスドルフ次元は3です。平面Hツリーとその3次元バージョンは、フォトニック結晶やメタマテリアルにおける人工電磁原子を構成することがわかっており、マイクロ波工学において潜在的な応用がある可能性があります。[ 9 ]
H ツリーは、隣接する線分間の角度が常に 90 度であるフラクタルキャノピーの一例です。境界矩形のすべての点に任意に近づくという性質から、それ自体は曲線ではありませんが、空間充填曲線にも似ています。[ 3 ]
H ツリーの線分の代わりに太い多角形の枝を用いた同じツリー構造のバリエーションは、ブノワ・マンデルブロによって定義され、マンデルブロツリーと呼ばれることもあります。これらのバリエーションでは、ツリーの葉と太い枝の重なりを避けるために、各レベルでサイズを縮小するスケールファクターは、わずかに大きくする必要があります。[ 10 ]
