H木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/30 05:39 UTC 版)
H木、H treeまたはH-Tree はフラクタル図形の1つであり、直線の両端に、その長さの1/√2の長さの垂線を追加し続けることによって構成される図形である。繰り返しパターンがアルファベットの "H" に似ているため、H木と呼ばれる。ハウスドルフ次元は2であり、矩形内の任意の点に対し、十分近いH木上の点が存在する。任意のステップにおいて、中心から端点までの距離がすべて等しい性質を利用し、VLSI設計とマイクロ波工学で用いられている。
構成
H木は、任意の長さの線分を元に、「その線分の両端に垂直な1/√2の長さの2本の線分を追加する」という処理を繰り返すことで構成できる[1]。
また、白銀比である1:√2の長方形から開始し、長辺を2等分し、その重心を直線で結ぶという処理でも構築できる。1:√2 = √2/2:1であるため、分割された長方形もまた白銀比の長方形である。他の比で表される長方形でも同様の処理は可能であるが、白銀比でない長方形では、奇数ステップと偶数ステップでは重心間の距離の比が一定ではない。
性質
H木は自己相似図形（フラクタル図形）であり、そのハウスドルフ次元は2である[2]。
矩形（白銀比の長方形）内の任意の点に対し、十分近いH木上の点が存在する。しかし、全ての点が「含まれる」わけではなく、例えば1ステップ目の線分に対する垂直二等分線はH木に含まれない。
応用
VLSIの設計において、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]。
脚注
- ^ 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.
- ^ Hou et al. (2008); Wen et al. (2002).
- ^ Weisstein, Eric W. "Mandelbrot Tree". MathWorld（英語）.
参考文献
- Bern, Marshall; Eppstein, David (1993), “Worst-case bounds for subadditive geometric graphs”, Proc. 9th Annual Symposium on Computational Geometry, Association for Computing Machinery, pp. 183–188, doi:10.1145/160985.161018.
- Browning, Sally A. (1980), The Tree Machine: A Highly Concurrent Computing Environment, Ph.D. thesis, California Institute of Technology.
- Burkis, J. (1991), “Clock tree synthesis for high performance ASICs”, IEEE International Conference on ASIC, pp. 9.8.1–9.8.4, doi:10.1109/ASIC.1991.242921.
- Hou, Bo; Xie, Hang; Wen, Weijia; Sheng, Ping (2008), “Three-dimensional metallic fractals and their photonic crystal characteristics”, Physical Review B 77: 125113, doi:10.1103/PhysRevB.77.125113.
- Kaloshin, Vadim; Saprykina, Maria (2012), “An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension”, Communications in Mathematical Physics 315 (3): 643–697, doi:10.1007/s00220-012-1532-x, MR 2981810.
- Leiserson, Charles E. (1980), “Area-efficient graph layouts”, 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), pp. 270–281, doi:10.1109/SFCS.1980.13.
- Nguyen, Quang Vinh; Huang, Mao Lin (2002), “A space-optimized tree visualization”, IEEE Symposium on Information Visualization, pp. 85–92, doi:10.1109/INFVIS.2002.1173152.
- Ullman, Jeffrey D. (1984), Computational Aspects of VSLI, Computer Science Press.
- Wen, Weijia; Zhou, Lei; Li, Jensen; Ge, Weikun; Chan, C. T.; Sheng, Ping (2002), Subwavelength photonic band gaps from planar fractals, 89, Physical Review Letters, p. 223901, doi:10.1103/PhysRevLett.89.223901.
参考図書
- Kabai, S. (2002), Mathematical Graphics I: Lessons in Computer Graphics Using Mathematica, Püspökladány, Hungary: Uniconstant, p. 231.
- Lauwerier, H. (1991), Fractals: Endlessly Repeated Geometric Figures, Princeton, NJ: Princeton University Press, pp. 1–2.
外部リンク
- >> 「H木」を含む用語の索引
- H木のページへのリンク
