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 the length of the line segments drawn at each stage by √2. Surprisingly, continuing this process will eventually result in a rectangle, or in other words, the H-fractal is a Peano curve. It is also an example of a fractal canopy, in which the angle between neighboring line segments is always 180 degrees. The boundary of the Mandelbrot set is a famous example of a fractal. ... In mathematics, the Hausdorff dimension is an extended non-negative real number associated to any metric space. ... The square root of 2 is equal to the length of the hypotenuse of a right triangle with legs of length 1. ... In geometry, a rectangle is defined as a quadrilateral where all four of its angles are right angles. ... Intuitively, a continuous curve in the 2-dimensional plane or in the 3-dimensional space can be thought of as the path of a continuously moving point. To eliminate the inherent vagueness of this notion, Jordan in 1887 introduced the following rigorous definition, which has since been adopted as the... Look up segment in Wiktionary, the free dictionary Segment may mean: Segment (biology), a repeated part of the metazoan body. ...

An alternative process that generates the same fractal set is to begin with a silver rectangle^[1] 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. It has been suggested that this article or section be merged into ISO 216. ... Centroid of a triangle In geometry, the centroid or barycenter of an object in -dimensional space is the intersection of all hyperplanes that divide into two parts of equal moment about the hyperplane. ...

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.^[2] Additionally, the H tree has been used as an interconnection network for VLSI multiprocessors,^[3] as a space efficient layout for trees in graph drawing,^[4] 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.^[5] In a synchronous digital system, the clock signal is used to define a time reference for the movement of data within that system. ... In electronics and especially synchronous digital circuits, a clock signal is a signal used to coordinate the actions of two or more circuits. ... As a branch of graph theory, Graph drawing applies topology and geometry to derive two- and three-dimensional representations of graphs. ... The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ...

Notes

A comparison of different paper sizes A4 is a standard paper size, defined by the international standard ISO 216 as 210×297 mm (roughly 8. ...

References

• Bern, M.; Eppstein, D. (1993). "Worst-case bounds for subadditive geometric graphs". Proc. 9th ACM Symposium on Computational Geometry: 183–188. 

• 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: 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: 85–92. DOI:10.1109/INFVIS.2002.1173152. 

• Ullman, Jeffrey D. (1984). Computational Aspects of VSLI. Computer Science Press. 

David Eppstein is a computer scientist at the Computer Science Department, Donald Bren School of Information and Computer Sciences, University of California, Irvine. ... A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ... A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ... Jeffrey D. Ullman (born November 22, 1942) is a renowned computer scientist. ...

External links

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