एच ट्री

Not to be confused with HTree, a Linux filesystem indexing structure.

एच पेड़ के पहले दस स्तर

भग्न ज्यामिति में, एच पेड़ एक फ्रैक्टल पेड़ संरचना है जो लंबवत रेखा खंडों से निर्मित होता है, प्रत्येक अगले बड़े आसन्न खंड से 2 के वर्गमूल के कारक से छोटा होता है। इसे इसलिए कहा जाता है क्योंकि इसका दोहराव वाला पैटर्न एच अक्षर जैसा दिखता है। इसमें हॉसडॉर्फ आयाम 2 है, और आयत में हर बिंदु के करीब मनमाने ढंग से आता है। इसके अनुप्रयोगों में वीएलएसआई डिजाइन और माइक्रोवेव इंजीनियरिंग शामिल हैं।

निर्माण

मनमाना लंबाई के एक रेखा खंड के साथ शुरू करके एक एच पेड़ का निर्माण किया जा सकता है, इसके अंतिम बिंदुओं के माध्यम से समकोण पर दो छोटे खंडों को खींचकर, और एक ही नस में जारी रखते हुए, प्रत्येक पर खींचे गए रेखा खंडों की लंबाई को कम (विभाजित) किया जा सकता है। चरण द्वारा ${\sqrt {2}}$. इस निर्माण का एक संस्करण भी परिभाषित किया जा सकता है जिसमें प्रत्येक पुनरावृत्ति की लंबाई को अनुपात से कम गुणा किया जाता है $1/{\sqrt {2}}$, लेकिन इस संस्करण के लिए परिणामी आकृति फ्रैक्टल सीमा के साथ, इसके बाउंडिंग आयत के केवल एक हिस्से को कवर करती है।

समान फ्रैक्टल सेट उत्पन्न करने वाली एक वैकल्पिक प्रक्रिया अनुपात में पक्षों के साथ एक आयत से शुरू होती है $1:{\sqrt {2}}$, और बार-बार इसे दो छोटे चांदी के आयतों में विभाजित करते हैं, प्रत्येक चरण में दो छोटे आयतों के दो केन्द्रक को एक रेखा खंड से जोड़ते हैं। इसी तरह की प्रक्रिया किसी अन्य आकार के आयतों के साथ की जा सकती है, लेकिन $1:{\sqrt {2}}$ आयत एक समान रूप से घटते हुए रेखा खंड आकार की ओर जाता है ${\sqrt {2}}$ प्रत्येक चरण पर कारक जबकि अन्य आयतों के लिए पुनरावर्ती निर्माण के विषम और सम स्तरों पर विभिन्न कारकों द्वारा लंबाई घट जाएगी।

गुण

एच पेड़ एक स्व-समानता है | स्व-समान फ्रैक्टल; इसका हॉसडॉर्फ आयाम 2 के बराबर है।

एच पेड़ के बिंदु मनमाने ढंग से एक आयत में हर बिंदु के करीब आते हैं (उपविभाजित आयतों के केन्द्रक द्वारा निर्माण में प्रारंभिक आयत के समान)। हालाँकि, इसमें आयत के सभी बिंदु शामिल नहीं हैं; उदाहरण के लिए, प्रारंभिक रेखा खंड (इस खंड के मध्य बिंदु के अलावा) के लंबवत द्विभाजक पर बिंदु शामिल नहीं हैं।

अनुप्रयोग

बड़े पैमाने पर एकीकरण डिज़ाइन में, H ट्री को एक पूर्ण बाइनरी ट्री के लेआउट के रूप में उपयोग किया जा सकता है, जो कुल क्षेत्रफल का उपयोग करता है जो ट्री के नोड्स की संख्या के अनुपात में होता है। इसके अतिरिक्त, H ट्री ग्राफ़ आरेखण में पेड़ों के लिए एक स्थान कुशल लेआउट बनाता है, और एक बिंदु सेट के निर्माण के हिस्से के रूप में जिसके लिए यात्रा विक्रेता समस्या के वर्ग किनारे की लंबाई का योग बड़ा है। यह आमतौर पर घड़ी वितरण नेटवर्क के रूप में उपयोग किया जाता है, चिप के सभी भागों में घड़ी घड़ी संकेत को रूट करने के लिए प्रत्येक भाग में समान प्रसार विलंब के साथ, और वीएलएसआई मल्टीप्रोसेसरों के लिए इंटरकनेक्शन नेटवर्क के रूप में भी इस्तेमाल किया गया है।

3-आयामी एच पेड़

प्लेनर एच ट्री को एच ट्री प्लेन की दिशा में लंबवत रेखा खंडों को जोड़कर त्रि-आयामी संरचना के लिए सामान्यीकृत किया जा सकता है। परिणामी त्रि-आयामी एच पेड़ में हॉसडॉर्फ आयाम 3 के बराबर है। प्लानर एच पेड़ और इसके त्रि-आयामी संस्करण को फोटोनिक क्रिस्टल और metamaterials में कृत्रिम विद्युत चुम्बकीय परमाणुओं का गठन करने के लिए पाया गया है और माइक्रोवेव इंजीनियरिंग में संभावित अनुप्रयोग हो सकते हैं।

संबंधित सेट

एच पेड़ की तुलना में तेज कोणों के साथ स्व-अतिव्यापी फ्रैक्टल चंदवा

एच ट्री फ्रैक्टल कैनोपी का एक उदाहरण है, जिसमें पड़ोसी रेखा खंडों के बीच का कोण हमेशा 180 डिग्री होता है। अपने बाउंडिंग आयत के हर बिंदु के करीब मनमाने ढंग से आने की अपनी संपत्ति में, यह एक जगह भरने वाला कर्व जैसा दिखता है, हालांकि यह स्वयं एक कर्व नहीं है।

टोपोलॉजी, एक एच ट्री में डेंड्रॉइड (टोपोलॉजी) के समान गुण होते हैं। हालांकि, वे dendroids नहीं हैं: dendroids बंद सेट होना चाहिए, और H पेड़ बंद नहीं हैं (उनका बंद होना संपूर्ण आयत है)।

एच पेड़ के लाइन खंडों के स्थान पर घनीभूत बहुभुज शाखाओं के साथ एक ही पेड़ की संरचना की विविधताओं को बेनोइट मंडेलब्रॉट द्वारा परिभाषित किया गया है, और कभी-कभी उन्हें मैंडेलब्रॉट पेड़ कहा जाता है। इन विविधताओं में, पेड़ की पत्तियों और उनकी मोटी शाखाओं के बीच अतिच्छादन से बचने के लिए, स्केल कारक जिसके द्वारा प्रत्येक स्तर पर आकार कम किया जाता है, उससे थोड़ा अधिक होना चाहिए ${\sqrt {2}}$.

संदर्भ

• Bern, Marshall; Eppstein, David (1993), "Worst-case bounds for subadditive geometric graphs", Proc. 9th Annual Symposium on Computational Geometry (PDF), Association for Computing Machinery, pp. 183–188, doi:10.1145/160985.161018, S2CID 14158914.
• 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, pp. 9.8.1–9.8.4, doi:10.1109/ASIC.1991.242921, S2CID 60985695.
• Hou, Bo; Xie, Hang; Wen, Weijia; Sheng, Ping (2008), "Three-dimensional metallic fractals and their photonic crystal characteristics" (PDF), Physical Review B, 77 (12): 125113, doi:10.1103/PhysRevB.77.125113.
• Kaloshin, Vadim; Saprykina, Maria (2012), "An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension", Communications in Mathematical Physics, 315 (3): 643–697, doi:10.1007/s00220-012-1532-x, MR 2981810, S2CID 253737197.
• Lauwerier, Hans (1991), Fractals: Endlessly Repeated Geometrical Figures, Princeton Science Library, vol. 6, translated by Gill-Hoffstadt, Sophia, Princeton University Press, ISBN 9780691024455
• Leiserson, Charles E. (1980), "Area-efficient graph layouts", 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), pp. 270–281, doi:10.1109/SFCS.1980.13, S2CID 15532332.
• Nguyen, Quang Vinh; Huang, Mao Lin (2002), "A space-optimized tree visualization", IEEE Symposium on Information Visualization, pp. 85–92, doi:10.1109/INFVIS.2002.1173152, S2CID 22192509.
• Ullman, Jeffrey D. (1984), Computational Aspects of VSLI, Computer Science Press.
• Wen, Weijia; Zhou, Lei; Li, Jensen; Ge, Weikun; Chan, C. T.; Sheng, Ping (2002), "Subwavelength photonic band gaps from planar fractals" (PDF), Physical Review Letters, 89 (22): 223901, doi:10.1103/PhysRevLett.89.223901, PMID 12485068.