H tree

Not to be confused with Htree, a Linux filesystem indexing structure.

The first ten levels of an H tree

The H tree (so called because its first two steps resemble the letter "H") is a family of fractal sets whose Hausdorff dimension is equal to 2. They can be constructed by starting with a line segment of arbitrary length, drawing two shorter segments at right angles to the first through its endpoints, and continuing in the same vein, reducing (dividing) the length of the line segments drawn at each stage by √2.^[1] Surprisingly, continuing this process will eventually come arbitrarily close to every point in a rectangle, or in other words, the H-fractal is a space-filling curve.^[2] It is also an example of a fractal canopy, in which the angle between neighboring line segments is always 180 degrees.

An alternative process that generates the same fractal set is to begin with a rectangle with sides in the ratio 1:√2, known as a "silver rectangle", and repeatedly bisect it into two smaller silver rectangles, at each stage connecting the two centroids of the two smaller rectangles by a line segment. A similar process can be performed with rectangles of any other shape, but the silver rectangle leads to the line segment size decreasing uniformly by a √2 factor at each step while for other rectangles the length will decrease by different factors at odd and even levels of the recursive construction.

The Mandelbrot Tree is a very closely related fractal using rectangles instead of line segments, slightly offset from the H-tree positions, in order to produce a more naturalistic appearance. To compensate for the increased width of its components and avoid self-overlap, the scale factor by which the size of the components is reduced at each level must be slightly greater than √2.

Applications

The H tree is commonly used in VLSI design as a clock distribution network for routing timing signals to all parts of a chip with equal propagation delays to each part.^[3] For the same reason, the H tree is used in arrays of microstrip antennas in order to get the radio signal to every individual microstrip antenna with equal propagation delay. Additionally, the H tree has been used as an interconnection network for VLSI multiprocessors,^[4] as a space efficient layout for trees in graph drawing,^[5] and as part of a construction of a point set for which the sum of squared edge lengths of the traveling salesman tour is large.^[6]

The planar H tree can be generalized to the three-dimensional structure via adding line segments on the direction perpendicular to the H tree plane.^[7] The resultant three-dimensional H tree has Hausdorff dimension equal to 3. The planar H tree and its three-dimensional version have been found to constitute artificial electromagnetic atoms in photonic crystals and metamaterials and might have potential applications in microwave engineering.^[7]

Notes

1. ^ "H-Fractal by Sándor Kabai, The Wolfram Demonstrations Project.
2. ^ Note, however, that it does not include all points of the rectangle; for instance, the perpendicular bisector of the initial line segment is not included.
3. ^ Ullman (1984); Burkis (1991).
4. ^ Browning (1980). See especially Figure 1.1.5, page 15.
5. ^ Nguyen and Huang (2002).
6. ^ Bern and Eppstein (1993).
7. ^ ^{a b} Hou (2008); Wen (2002).

References

• Bern, M.; Eppstein, D. (1993). "Worst-case bounds for subadditive geometric graphs". Proc. 9th ACM Symposium on Computational Geometry. pp. 183–188. http://www.ics.uci.edu/~eppstein/pubs/BerEpp-SCG-93.pdf. 
• Browning, Sally A. (1980). The Tree Machine: A Highly Concurrent Computing Environment. Ph.D. thesis. California Institute of Technology. http://caltechcstr.library.caltech.edu/338/. 
• 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. 
• 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. 
• B. Hou, H. Xie, W. Wen, and P. Sheng (2008). “Three-dimensional metallic fractals and their photonic crystal characteristics”. Phys. Rev. B 77, 125113. http://prb.aps.org/abstract/PRB/v77/i12/e125113. 
• W. Wen, L. Zhou, J. Li, W. Ge, C. T. Chan, and P. Sheng (2002). “Subwavelength Photonic Band Gaps from Planar Fractals”. Phys. Rev. Lett. 89, 223901. http://prl.aps.org/abstract/PRL/v89/i22/e223901. 

Further reading

• Kabai, S. Mathematical Graphics I: Lessons in Computer Graphics Using Mathematica. Püspökladány, Hungary: Uniconstant, p. 231, 2002.
• Lauwerier, H. Fractals: Endlessly Repeated Geometric Figures. Princeton, NJ: Princeton University Press, pp. 1-2, 1991.

External links

• Famous Fractals - H-fractal
• Weisstein, Eric W., "H-Fractal" from MathWorld.
• Weisstein, Eric W., "Mandelbrot Tree" from MathWorld.