एच पेड़

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

H वृक्ष के पहले दस स्तर

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

निर्माण

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

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

गुण

एच वृक्ष एक स्व-समानता | स्व-समान भग्न है; इसका हॉसडॉर्फ आयाम 2 के बराबर है।

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

अनुप्रयोग

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

3-आयामी एच वृक्ष

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

संबंधित सेट

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

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

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

एच पेड़ के रेखा खंडों के स्थान पर मोटी बहुभुज शाखाओं के साथ एक ही पेड़ की संरचना की विविधताओं को बेनोइट मैंडेलब्रॉट द्वारा परिभाषित किया गया है, और कभी-कभी उन्हें मैंडेलब्रॉट पेड़ भी कहा जाता है। इन विविधताओं में, पेड़ की पत्तियों और उनकी मोटी शाखाओं के बीच ओवरलैप से बचने के लिए, स्केल फैक्टर जिसके द्वारा प्रत्येक स्तर पर आकार कम किया जाता है, उससे थोड़ा अधिक होना चाहिए ${\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.