In fractal geometry, the H tree is a fractal tree structure constructed from perpendicular line segments, each smaller by a factor of the 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 2, and comes arbitrarily close to every point in a rectangle. Its applications include VLSI design and microwave engineering.

Construction

An H tree can be constructed by starting with a line segment., but for this variant the resulting shape covers only part of its bounding rectangle, with a fractal boundary.

, and repeatedly bisect it into two smaller silver rectangles, at each stage connecting the two centroids 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 fractal; its Hausdorff dimension is equal to 2.

The points of the H tree come arbitrarily close to every point in a rectangle (the same as the starting rectangle in the constructing by centroids of subdivided rectangles). It follows that its topological closure 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 design, the H tree may be used as the layout for a complete binary tree using a total area that is proportional to the number of nodes of the tree. Additionally, the H tree forms a space efficient layout for trees in graph drawing, 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. It is commonly used as a clock distribution network for routing timing signals to all parts of a chip with equal propagation delays to each part, and has also been used as an interconnection network for VLSI multiprocessors.

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. 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.

Related sets

The H tree is an example of a 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, although it is not itself a curve.

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.

Notes

References

• .

• .

• .

• .

• .

• .

• .

• .

• .