H tree
Encyclopedia
Fractal
A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
sets whose Hausdorff dimension
Hausdorff dimension
thumb|450px|Estimating the Hausdorff dimension of the coast of Great BritainIn mathematics, the Hausdorff dimension is an extended non-negative real number associated with any metric space. The Hausdorff dimension generalizes the notion of the dimension of a real vector space...
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
Square root of 2
The square root of 2, often known as root 2, is the positive algebraic number that, when multiplied by itself, gives the number 2. It is more precisely called the principal square root of 2, to distinguish it from the negative number with the same property.Geometrically the square root of 2 is the...
. Surprisingly, continuing this process will eventually come arbitrarily close to every point in a rectangle
Rectangle
In Euclidean plane geometry, a rectangle is any quadrilateral with four right angles. The term "oblong" is occasionally used to refer to a non-square rectangle...
, or in other words, the H-fractal is a space-filling curve
Space-filling curve
In mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square...
. 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 centroid
Centroid
In geometry, the centroid, geometric center, or barycenter of a plane figure or two-dimensional shape X is the intersection of all straight lines that divide X into two parts of equal moment about the line. Informally, it is the "average" of all points of X...
s 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 signalsClock signal
In electronics and especially synchronous digital circuits, a clock signal is a particular type of signal that oscillates between a high and a low state and is utilized like a metronome to coordinate actions of circuits...
to all parts of a chip with equal propagation delays to each part. For the same reason, the H tree is used in arrays of microstrip antenna
Microstrip antenna
In telecommunication, there are several types of microstrip antennas the most common of which is the microstrip patch antenna or patch antenna...
s 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, as a space efficient layout for trees in graph drawing
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, cartography, and bioinformatics...
, 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.
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
Hausdorff dimension
thumb|450px|Estimating the Hausdorff dimension of the coast of Great BritainIn mathematics, the Hausdorff dimension is an extended non-negative real number associated with any metric space. The Hausdorff dimension generalizes the notion of the dimension of a real vector space...
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.
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.