| 词条 | H tree |
| 释义 |
In fractal geometry, the H tree, or T-branching, 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. ConstructionAn 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 {{sqrt|2}}.[1] An alternative process that generates the same fractal set is to begin with a rectangle with sides in the ratio 1:{{sqrt|2}}, known as a "silver rectangle", 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 {{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. PropertiesThe H tree is a self-similar fractal; its Hausdorff dimension is equal to 2.{{sfnp|Kaloshin|Saprykina|2012}} 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 perpendicular bisector of the initial line segment is not included. ApplicationsIn 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.{{sfnp|Leiserson|1980}} Additionally, the H tree forms a space efficient layout for trees in graph drawing,{{sfnp|Nguyen|Huang|2002}} 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.{{sfnp|Bern|Eppstein|1993}} 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,[2] and has also been used as an interconnection network for VLSI multiprocessors.[3] For the same reason, the H tree is used in arrays of microstrip antennas in order to get the radio signal to every individual microstrip antenna with equal propagation delay. 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.[4] 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.[4] Related sets{{multiple image| align = | direction = horizontal | width = 150 | header = | image1 = Golden Square fractal 6.svg | caption1 = Square branches, related by the golden ratio | image2 = Half square fractal 5.svg | caption2 = Squares branches, related by 1/2 | footer = }} The H tree is an example of a fractal canopy, 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, 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). 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 {{sqrt|2}}.[5] See also
Notes1. ^H-Fractal, Sándor Kabai, The Wolfram Demonstrations Project. 2. ^{{harvtxt|Ullman|1984}}; {{harvtxt|Burkis|1991}}. 3. ^{{harvtxt|Browning|1980}}. See especially Figure 1.1.5, page 15. 4. ^1 {{harvtxt|Hou|Xie|Wen|Sheng|2008}}; {{harvtxt|Wen|Zhou|Li|Ge|2002}}. 5. ^{{mathworld|title=Mandelbrot Tree|urlname=MandelbrotTree}} References{{refbegin}}
| last1 = Bern | first1 = Marshall | last2 = Eppstein | first2 = David | author2-link = David Eppstein | contribution = Worst-case bounds for subadditive geometric graphs | doi = 10.1145/160985.161018 | pages = 183–188 | publisher = Association for Computing Machinery | title = Proc. 9th Annual Symposium on Computational Geometry | url = http://www.ics.uci.edu/~eppstein/pubs/BerEpp-SCG-93.pdf | year = 1993}}.
| last = Browning | first = Sally A. | publisher = California Institute of Technology | series = Ph.D. thesis | title = The Tree Machine: A Highly Concurrent Computing Environment | url = http://authors.library.caltech.edu/26932/ | year = 1980}}.
| last = Burkis | first = J. | contribution = Clock tree synthesis for high performance ASICs | doi = 10.1109/ASIC.1991.242921 | pages = 9.8.1–9.8.4 | title = IEEE International Conference on ASIC | year = 1991}}.
| last1 = Hou | first1 = Bo | last2 = Xie | first2 = Hang | last3 = Wen | first3 = Weijia | last4 = Sheng | first4 = Ping | doi = 10.1103/PhysRevB.77.125113 | journal = Physical Review B | page = 125113 | title = Three-dimensional metallic fractals and their photonic crystal characteristics | volume = 77 | year = 2008}}.
| last1 = Kaloshin | first1 = Vadim | last2 = Saprykina | first2 = Maria | doi = 10.1007/s00220-012-1532-x | issue = 3 | journal = Communications in Mathematical Physics | mr = 2981810 | pages = 643–697 | title = An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension | volume = 315 | year = 2012}}.
| last = Leiserson | first = Charles E. | author-link = Charles E. Leiserson | contribution = Area-efficient graph layouts | doi = 10.1109/SFCS.1980.13 | pages = 270–281 | title = 21st Annual Symposium on Foundations of Computer Science (FOCS 1980) | year = 1980}}.
| last1 = Nguyen | first1 = Quang Vinh | last2 = Huang | first2 = Mao Lin | contribution = A space-optimized tree visualization | doi = 10.1109/INFVIS.2002.1173152 | pages = 85–92 | title = IEEE Symposium on Information Visualization | year = 2002}}.
| last = Ullman | first = Jeffrey D. | author-link = Jeffrey D. Ullman | publisher = Computer Science Press | title = Computational Aspects of VSLI | year = 1984}}.
| last1 = Wen | first1 = Weijia | last2 = Zhou | first2 = Lei | last3 = Li | first3 = Jensen | last4 = Ge | first4 = Weikun | last5 = Chan | first5 = C. T. | last6 = Sheng | first6 = Ping | doi = 10.1103/PhysRevLett.89.223901 | page = 223901 | publisher = Physical Review Letters | title = Subwavelength photonic band gaps from planar fractals | volume = 89 | year = 2002| url = http://repository.ust.hk/ir/bitstream/1783.1-49380/1/PhysRevLett.89.223901.pdf}}.{{refend}} Further reading
| last = Kabai | first = S. | location = Püspökladány, Hungary | page = 231 | publisher = Uniconstant | title = Mathematical Graphics I: Lessons in Computer Graphics Using Mathematica | year = 2002}}.
| last = Lauwerier | first = H. | location = Princeton, NJ | pages = 1–2 | publisher = Princeton University Press | title = Fractals: Endlessly Repeated Geometric Figures | year = 1991}}. External links
3 : Fractals|Trees (data structures)|Clock signal |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。