# H tree

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/H_tree
> Markdown URL: https://mediated.wiki/source/H_tree.md
> Source: https://en.wikipedia.org/wiki/H_tree
> Source revision: 1346671559
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Right-angled fractal canopy

Not to be confused with [HTree](/source/HTree), a Linux filesystem indexing structure.

The first ten levels of an H tree

In [fractal geometry](/source/Fractal_geometry), the **H tree** is a [fractal](/source/Fractal) tree structure constructed from [perpendicular](/source/Perpendicular) [line segments](/source/Line_segment), each smaller by a factor of the [square root of 2](/source/Square_root_of_2) from the next larger adjacent segment. It is so called because its repeating pattern resembles the letter "H". It has [Hausdorff dimension](/source/Hausdorff_dimension) 2, and comes arbitrarily close to every point in a [rectangle](/source/Rectangle). Its applications include [VLSI](/source/VLSI) design and microwave engineering.

## Construction

An H tree can be constructed by starting with a [line segment](/source/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 {\displaystyle {\sqrt {2}}} .[1] A variant of this construction could also be defined in which the length at each iteration is multiplied by a ratio less than 1 / 2 {\displaystyle 1/{\sqrt {2}}} , but for this variant the resulting shape covers only part of its bounding rectangle, with a fractal boundary.[2]

An alternative process that generates the same fractal set is to begin with a rectangle with sides in the ratio 1 : 2 {\displaystyle 1:{\sqrt {2}}} , and repeatedly bisect it into two smaller [silver](/source/Silver_ratio) rectangles, at each stage connecting the two [centroids](/source/Centroid) of the two smaller rectangles by a line segment. A similar process can be performed with rectangles of any other shape, but the 1 : 2 {\displaystyle 1:{\sqrt {2}}} rectangle leads to the line segment size decreasing uniformly by a 2 {\displaystyle {\sqrt {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.

## Properties

The H tree is a [self-similar](/source/Self-similarity) [fractal](/source/Fractal); its [Hausdorff dimension](/source/Hausdorff_dimension) is equal to 2.[2]

The points of the H tree come arbitrarily close to every point in a [rectangle](/source/Rectangle) (the same as the starting rectangle in the constructing by centroids of subdivided rectangles).[3] It follows that its [topological closure](/source/Closure_(topology)) is the entire rectangle. However, it does not include all points of the rectangle; for instance, the points on the perpendicular bisector of the initial line segment (other than the midpoint of this segment) are not included.

## Applications

In [VLSI](/source/Very_Large_Scale_Integration) design, the H tree may be used as the layout for a [complete binary tree](/source/Complete_binary_tree) using a total area that is proportional to the number of nodes of the tree.[4] Additionally, the H tree forms a space efficient layout for trees in [graph drawing](/source/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](/source/Traveling_salesman_problem) is large.[6] It is commonly used as a [clock distribution network](/source/Clock_distribution_network) for routing [timing signals](/source/Clock_signal) to all parts of a chip with equal propagation delays to each part,[7] and has also been used as an interconnection network for VLSI multiprocessors.[8]

3-dimensional H tree

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.[9] The resultant three-dimensional H tree has [Hausdorff dimension](/source/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](/source/Photonic_crystals) and [metamaterials](/source/Metamaterials) and might have potential applications in microwave engineering.[9]

## Related sets

14 steps of the Fractal Canopy tree, animated.

The H tree is an example of a [fractal canopy](/source/Fractal_canopy), in which the angle between neighboring line segments is always 90 degrees. In its property of coming arbitrarily close to every point of its bounding rectangle, it also resembles a [space-filling curve](/source/Space-filling_curve), although it is not itself a curve.[3]

Variations of the same tree structure with thickened polygonal branches in place of the line segments of the H tree have been defined by [Benoit Mandelbrot](/source/Benoit_Mandelbrot), and are sometimes called the Mandelbrot tree. In these variations, to avoid overlaps between the leaves of the tree and their thickened branches, the scale factor by which the size is reduced at each level must be slightly greater than 2 {\displaystyle {\sqrt {2}}} .[10]

## Notes

1. **[^](#cite_ref-FOOTNOTELauwerier19911–2_1-0)** [Lauwerier (1991)](#CITEREFLauwerier1991), pp. 1–2.

1. ^ [***a***](#cite_ref-FOOTNOTEKaloshinSaprykina2012_2-0) [***b***](#cite_ref-FOOTNOTEKaloshinSaprykina2012_2-1) [Kaloshin & Saprykina (2012)](#CITEREFKaloshinSaprykina2012).

1. ^ [***a***](#cite_ref-FOOTNOTEdos_SantosSilvaGomes_D'AssunçãoRamalho_Minervino2013_3-0) [***b***](#cite_ref-FOOTNOTEdos_SantosSilvaGomes_D'AssunçãoRamalho_Minervino2013_3-1) [dos Santos et al. (2013)](#CITEREFdos_SantosSilvaGomes_D'AssunçãoRamalho_Minervino2013).

1. **[^](#cite_ref-FOOTNOTELeiserson1980_4-0)** [Leiserson (1980)](#CITEREFLeiserson1980).

1. **[^](#cite_ref-FOOTNOTENguyenHuang2002_5-0)** [Nguyen & Huang (2002)](#CITEREFNguyenHuang2002).

1. **[^](#cite_ref-FOOTNOTEBernEppstein1993_6-0)** [Bern & Eppstein (1993)](#CITEREFBernEppstein1993).

1. **[^](#cite_ref-7)** [Ullman (1984)](#CITEREFUllman1984); [Burkis (1991)](#CITEREFBurkis1991).

1. **[^](#cite_ref-8)** [Browning (1980)](#CITEREFBrowning1980). See especially Figure 1.1.5, page 15.

1. ^ [***a***](#cite_ref-Hou&Wen_9-0) [***b***](#cite_ref-Hou&Wen_9-1) [Hou et al. (2008)](#CITEREFHouXieWenSheng2008); [Wen et al. (2002)](#CITEREFWenZhouLiGe2002).

1. **[^](#cite_ref-FOOTNOTELauwerier199171–73_10-0)** [Lauwerier (1991)](#CITEREFLauwerier1991), pp. 71–73.

## References

- Bern, Marshall; [Eppstein, David](/source/David_Eppstein) (1993), "Worst-case bounds for subadditive geometric graphs", [*Proc. 9th Annual Symposium on Computational Geometry*](https://www.ics.uci.edu/~eppstein/pubs/BerEpp-SCG-93.pdf) (PDF), [Association for Computing Machinery](/source/Association_for_Computing_Machinery), pp. 183–188, [doi](/source/Doi_(identifier)):[10.1145/160985.161018](https://doi.org/10.1145%2F160985.161018), [ISBN](/source/ISBN_(identifier)) [0-89791-582-8](https://en.wikipedia.org/wiki/Special:BookSources/0-89791-582-8), [S2CID](/source/S2CID_(identifier)) [14158914](https://api.semanticscholar.org/CorpusID:14158914).

- Browning, Sally A. (1980), [*The Tree Machine: A Highly Concurrent Computing Environment*](https://web.archive.org/web/20120716071923/http://authors.library.caltech.edu/26932/), Ph.D. thesis, California Institute of Technology, archived from [the original](http://authors.library.caltech.edu/26932/) on 2012-07-16, retrieved 2012-11-28.

- Burkis, J. (1991), "Clock tree synthesis for high performance ASICs", *IEEE International Conference on ASIC*, pp. 9.8.1–9.8.4, [doi](/source/Doi_(identifier)):[10.1109/ASIC.1991.242921](https://doi.org/10.1109%2FASIC.1991.242921), [ISBN](/source/ISBN_(identifier)) [0-7803-0101-3](https://en.wikipedia.org/wiki/Special:BookSources/0-7803-0101-3), [S2CID](/source/S2CID_(identifier)) [60985695](https://api.semanticscholar.org/CorpusID:60985695).

- dos Santos, Albanisa F.; Silva, Paulo H. Da F; Gomes D'Assunção, Adaildo; Ramalho Minervino, Diego (August 2013), "Microstrip bandstop filters with H-fractal stubs", *2013 SBMO/IEEE MTT-S International Microwave & Optoelectronics Conference (IMOC)*, IEEE, pp. 1–5, [doi](/source/Doi_(identifier)):[10.1109/imoc.2013.6646575](https://doi.org/10.1109%2Fimoc.2013.6646575)

- Hou, Bo; Xie, Hang; Wen, Weijia; Sheng, Ping (2008), ["Three-dimensional metallic fractals and their photonic crystal characteristics"](https://repository.ust.hk/ir/bitstream/1783.1-25969/1/PhysRevB.77.125113.pdf) (PDF), *[Physical Review B](/source/Physical_Review_B)*, **77** (12) 125113, [Bibcode](/source/Bibcode_(identifier)):[2008PhRvB..77l5113H](https://ui.adsabs.harvard.edu/abs/2008PhRvB..77l5113H), [doi](/source/Doi_(identifier)):[10.1103/PhysRevB.77.125113](https://doi.org/10.1103%2FPhysRevB.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, [Bibcode](/source/Bibcode_(identifier)):[2012CMaPh.315..643K](https://ui.adsabs.harvard.edu/abs/2012CMaPh.315..643K), [doi](/source/Doi_(identifier)):[10.1007/s00220-012-1532-x](https://doi.org/10.1007%2Fs00220-012-1532-x), [MR](/source/MR_(identifier)) [2981810](https://mathscinet.ams.org/mathscinet-getitem?mr=2981810), [S2CID](/source/S2CID_(identifier)) [253737197](https://api.semanticscholar.org/CorpusID:253737197).

- Lauwerier, Hans (1991), *Fractals: Endlessly Repeated Geometrical Figures*, Princeton Science Library, vol. 6, translated by Gill-Hoffstadt, Sophia, Princeton University Press, [ISBN](/source/ISBN_(identifier)) [978-0-691-02445-5](https://en.wikipedia.org/wiki/Special:BookSources/978-0-691-02445-5)

- [Leiserson, Charles E.](/source/Charles_E._Leiserson) (1980), "Area-efficient graph layouts", *21st Annual Symposium on Foundations of Computer Science (FOCS 1980)*, pp. 270–281, [doi](/source/Doi_(identifier)):[10.1109/SFCS.1980.13](https://doi.org/10.1109%2FSFCS.1980.13), [S2CID](/source/S2CID_(identifier)) [15532332](https://api.semanticscholar.org/CorpusID:15532332).

- Nguyen, Quang Vinh; Huang, Mao Lin (2002), "A space-optimized tree visualization", *IEEE Symposium on Information Visualization*, pp. 85–92, [doi](/source/Doi_(identifier)):[10.1109/INFVIS.2002.1173152](https://doi.org/10.1109%2FINFVIS.2002.1173152), [ISBN](/source/ISBN_(identifier)) [0-7695-1751-X](https://en.wikipedia.org/wiki/Special:BookSources/0-7695-1751-X), [S2CID](/source/S2CID_(identifier)) [22192509](https://api.semanticscholar.org/CorpusID:22192509).

- [Ullman, Jeffrey D.](/source/Jeffrey_D._Ullman) (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"](https://repository.ust.hk/ir/bitstream/1783.1-49380/1/PhysRevLett.89.223901.pdf) (PDF), *[Physical Review Letters](/source/Physical_Review_Letters)*, **89** (22) 223901, [Bibcode](/source/Bibcode_(identifier)):[2002PhRvL..89v3901W](https://ui.adsabs.harvard.edu/abs/2002PhRvL..89v3901W), [doi](/source/Doi_(identifier)):[10.1103/PhysRevLett.89.223901](https://doi.org/10.1103%2FPhysRevLett.89.223901), [PMID](/source/PMID_(identifier)) [12485068](https://pubmed.ncbi.nlm.nih.gov/12485068).

v t e Fractals Characteristics Fractal dimensions Assouad Box-counting Higuchi Correlation Hausdorff Packing Topological Recursion Self-similarity Iterated function system Barnsley fern Cantor set Koch snowflake Menger sponge Sierpiński carpet Sierpiński triangle Apollonian gasket Fibonacci word Space-filling curve Blancmange curve De Rham curve Minkowski Dragon curve Hilbert curve Koch curve Lévy C curve Moore curve Peano curve Sierpiński curve Z-order curve String T-square n-flake Vicsek fractal Gosper curve Pythagoras tree Weierstrass function Strange attractor Multifractal system L-system Fractal canopy Space-filling curve H tree Escape-time fractals Burning Ship fractal Julia set Filled Newton fractal Douady rabbit Lyapunov fractal Mandelbrot set Misiurewicz point Multibrot set Newton fractal Tricorn Mandelbox Mandelbulb Rendering techniques Buddhabrot Orbit trap Pickover stalk Random fractals Brownian motion Brownian tree Brownian motor Fractal landscape Lévy flight Percolation theory Self-avoiding walk People Michael Barnsley Georg Cantor Bill Gosper Felix Hausdorff Desmond Paul Henry Gaston Julia Niels Fabian Helge von Koch Paul Lévy Aleksandr Lyapunov Benoit Mandelbrot Hamid Naderi Yeganeh Lewis Fry Richardson Wacław Sierpiński Other Coastline paradox Fractal art List of fractals by Hausdorff dimension The Fractal Geometry of Nature (1982 book) The Beauty of Fractals (1986 book) Chaos: Making a New Science (1987 book) Kaleidoscope Chaos theory

---
Adapted from the Wikipedia article [H tree](https://en.wikipedia.org/wiki/H_tree) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/H_tree?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.