In
fractal geometry
In mathematics, a fractal is a geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fractals appear similar at various scales, as illu ...
, the H tree is a
fractal tree structure constructed from
perpendicular
In elementary geometry, two geometric objects are perpendicular if they intersect at a right angle (90 degrees or π/2 radians). The condition of perpendicularity may be represented graphically using the ''perpendicular symbol'', ⟂. It ca ...
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
In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was first introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of ...
2, and comes arbitrarily close to every point in a
rectangle. Its applications include
VLSI
Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) ...
design and microwave engineering.
Construction
An H tree 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
. A variant of this construction could also be defined in which the length at each iteration is multiplied by a ratio less than
, but for this variant the resulting shape covers only part of its bounding rectangle, with a fractal boundary.
An alternative process that generates the same fractal set is to begin with a rectangle with sides in the ratio
, and repeatedly bisect it into two smaller silver rectangles, at each stage connecting the two
centroid
In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any ...
s of the two smaller rectangles by a line segment. A similar process can be performed with rectangles of any other shape, but the
rectangle leads to the line segment size decreasing uniformly by a
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
In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was first introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of ...
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). 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
Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) ...
design, the H tree may be used as the layout for a
complete binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary tr ...
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
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, car ...
, 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
In electronics and especially synchronous digital circuits, a clock signal (historically also known as ''logic beat'') oscillates between a high and a low state and is used like a metronome to coordinate actions of digital circuits.
A clock sig ...
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.
[. See especially Figure 1.1.5, page 15.]
![3D H-fractal](https://upload.wikimedia.org/wikipedia/commons/c/cc/3D_H-fractal.png)
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
In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was first introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of ...
equal to 3. The planar H tree and its three-dimensional version have been found to constitute artificial electromagnetic atoms in
photonic crystals
A photonic crystal is an optical nanostructure in which the refractive index changes periodically. This affects the propagation of light in the same way that the structure of natural crystals gives rise to X-ray diffraction and that the atomic ...
and
metamaterials
A metamaterial (from the Greek word μετά ''meta'', meaning "beyond" or "after", and the Latin word ''materia'', meaning "matter" or "material") is any material engineered to have a property that is not found in naturally occurring materials. ...
and might have potential applications in microwave engineering.
[
]
Related sets
The H tree is an example of a fractal canopy
In geometry, a fractal canopy, a type of fractal tree, is one of the easiest-to-create types of fractals. Each canopy is created by splitting a line segment into two smaller segments at the end (symmetric binary tree), and then splitting the tw ...
, in which the angle between neighboring line segments is always 180 degrees. In its property of coming arbitrarily close to every point of its bounding rectangle, it also resembles a space-filling curve
In mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square (or more generally an ''n''-dimensional unit hypercube). Because Giuseppe Peano (1858–1932) was the first to discover one, spa ...
, although it is not itself a curve.
Topologically, an H tree has properties similar to those of a dendroid. However, they are not dendroids: dendroids must be closed sets, and H trees are not closed (their closure is the whole rectangle).
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, 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 .
Notes
References
*.
*.
*.
*.
*.
*
*.
*.
*.
*.
{{Fractals
Fractals
Trees (data structures)
Clock signal