View source for यूक्लिडियन न्यूनतम प्रसारित ट्री

{{Short description|Shortest network connecting points}}

[[Image:Euclidean minimum spanning tree.svg|thumb|300px|right|विमान में 25 यादृच्छिक बिंदुओं का यूक्लिडियन न्यूनतम प्रसारित हुआ ट्री ]][[यूक्लिडियन विमान]] या उच्च-आयामी यूक्लिडियन अंतरिक्ष में बिंदुओं के एक सीमित समुच्चय का एक '''यूक्लिडियन न्यूनतम प्रसारित ट्री''' बिंदुओं को [[रेखा खंड|रेखा खंडों]] की एक प्रणाली द्वारा बिंदुओं के साथ अंत बिंदु के रूप में जोड़ता है, जिससे खंडों की कुल लंबाई कम हो जाती है। इसमें कोई भी दो बिंदु रेखा खंडों के माध्यम से एक पथ के साथ एक दूसरे तक पहुंच सकते हैं। इस प्रकार पूर्ण ग्राफ़ के न्यूनतम प्रसारित हुए ट्री के रूप में पाया जा सकता है जिसमें बिंदुओं को शीर्ष के रूप में और बिंदुओं के मध्य [[यूक्लिडियन दूरी]] को किनारे के धार भार के रूप में पाया जा सकता है।

न्यूनतम प्रसारित हुए ट्री के किनारे कम से कम 60° के कोण पर मिलते हैं, अधिकतम छह से एक शीर्ष तक है। उच्च आयामों में, प्रति शीर्ष किनारों की संख्या स्पर्शरेखा [[इकाई क्षेत्र]] की [[चुंबन संख्या]] से सीमित होती है। एक [[इकाई वर्ग]] में बिंदुओं के लिए किनारों की कुल लंबाई, बिंदुओं की संख्या के वर्गमूल के अधिकतम आनुपातिक होती है। प्रत्येक किनारा विमान के एक खाली क्षेत्र में स्थित होता है, और इन क्षेत्रों का उपयोग यह सिद्ध करने के लिए किया जा सकता है कि यूक्लिडियन न्यूनतम प्रसारित हुए ट्री सापेक्ष निकटतम ग्राफ और डेलाउने त्रिकोण सहित अन्य [[ज्यामितीय ग्राफ]] का एक उपग्राफ होता है। इस प्रकार डेलाउने त्रिभुज का निर्माण करके और फिर एक ग्राफ़ [[न्यूनतम फैलाव वाला पेड़|न्यूनतम प्रसारित व वाला ट्री]] कलन विधि लागू करके, न्यूनतम स्पैनिंग ट्री <math>n</math> दिए गए समतल बिंदु समय <math>O(n\log n)</math> पर पाए जा सकते हैं, जैसा कि [[बड़ा ओ अंकन|बड़े O अंकन]] में व्यक्त किया गया है। यह गणना के कुछ प्रारूप में सर्वश्रेष्ठ होता है, चूकिं पूर्णांक निर्देशांक वाले बिंदुओं के लिए स्पष्ट [[यादृच्छिक एल्गोरिदम|यादृच्छिक कलन विधि]] उपस्थित होते हैं। इस प्रकार उच्च आयामों वाले बिंदुओं के लिए, एक सर्वश्रेष्ठ कलन विधि ढूंढना एक [[खुली समस्या]] बनी हुई है।

==परिभाषा और संबंधित समस्याएँ==
एक यूक्लिडियन न्यूनतम प्रसारित हुए ट्री, के एक समुच्चय के लिए <math>n</math> यूक्लिडियन विमान या यूक्लिडियन स्पेस में बिंदु, रेखा खंडों की एक प्रणाली होती होती है, जिसमें मात्र दिए गए बिंदु उनके अंतिम बिंदु होते हैं, जिनके संघ में एक जुड़े हुए समुच्चय के सभी बिंदु सम्मलित होते हैं, और जिसमें ऐसी किसी भी प्रणाली की न्यूनतम संभव कुल लंबाई होती है। ऐसे नेटवर्क में खंडों का [[बहुभुज]] वलय नहीं हो सकता; यदि कोई अस्तित्व में है, तो बहुभुज के एक किनारे को हटाकर नेटवर्क को छोटा किया जा सकता है। इसलिए, न्यूनतम लंबाई वाला नेटवर्क एक ट्री (ग्राफ़ सिद्धांत) बनाता है। यह अवलोकन समतुल्य परिभाषा की ओर ले जाता है कि यूक्लिडियन न्यूनतम प्रसारित हुए ट्री, न्यूनतम कुल लंबाई के दिए गए बिंदुओं के जोड़े के मध्य रेखा खंडों का एक ट्री होता है।{{r|gowros}} इस प्रकार उसी ट्री को भारित पूर्ण ग्राफ के न्यूनतम प्रसारित हुए ट्री के रूप में भी वर्णित किया जा सकता है, जिसमें दिए गए बिंदु इसके शीर्ष के रूप में होते हैं और बिंदुओं के मध्य की दूरी किनारे के वजन के रूप में होती है।{{r|shahoe}} समान बिंदुओं पर एक से अधिक न्यूनतम प्रसारित हुए ट्री हो सकते हैं। उदाहरण के लिए, एक [[नियमित बहुभुज]] के शीर्षों के लिए, बहुभुज के किसी भी किनारे को हटाने से न्यूनतम प्रसारित हुए ट्री का निर्माण होता है।{{r|bdek}}

यूक्लिडियन मिनिमम स्पैनिंग ट्री पर प्रकाशन सामान्यतः इसे ईएमएसटी के रूप में संक्षिप्त करते हैं।{{r|aesw|mrg}} इन्हें ज्यामितीय न्यूनतम प्रसारित हुए ट्री भी कहा जा सकता है,{{r|clarkson|monsur}} लेकिन उस शब्द का उपयोग सामान्यतः गैर-यूक्लिडियन दूरियों वाले ज्यामितीय स्थानों के लिए किया जा सकता है, जैसे कि {{math|''L''<sup>''p''</sup>}} स्पेस।{{r|nzz}} जब यूक्लिडियन बिंदु समुच्चयों का संदर्भ स्पष्ट हो, तो उन्हें मात्र न्यूनतम प्रसारित हुए ट्री कहा जा सकता है।{{r|frakau|king|kln}}

इस प्रकार कई अन्य मानक ज्यामितीय नेटवर्क यूक्लिडियन न्यूनतम प्रसारित हुए ट्री से निकटता से संबंधित हैं:
*स्टाइनर ट्री समस्या फिर से सभी दिए गए बिंदुओं को जोड़ने वाले रेखा खंडों की एक प्रणाली की अन्वेषण करती है, लेकिन खंडों को मात्र दिए गए बिंदुओं पर प्रारम्भ और समाप्त करने की आवश्यकता के बिना। इस समस्या में, अतिरिक्त बिंदुओं को खंड समापन बिंदु के रूप में जोड़ा जा सकता है, जिससे स्टीनर ट्री न्यूनतम प्रसारित हुए ट्री से छोटा हो सकता है।{{r|gilpol}}
*यूक्लिडियन [[ट्रैवलिंग सेल्समैन की समस्या]] में, कनेक्टिंग लाइन सेगमेंट को दिए गए बिंदुओं पर प्रारम्भ और समाप्त होना चाहिए, जैसे कि प्रसारित हुए ट्री और स्टीनर ट्री के विपरीत; इसके अतिरिक्त, प्रत्येक बिंदु अधिकतम दो रेखा खंडों को छू सकता है, इसलिए परिणाम एक [[बहुभुज श्रृंखला]] बनाता है। इस प्रतिबंध के कारण, सर्वश्रेष्ठ पथ यूक्लिडियन न्यूनतम प्रसारित हुए ट्री से अधिक लंबा हो सकता है, परन्तु अधिकतम दोगुना लंबा होता है।{{r|shahoe}}
*[[ज्यामितीय स्पैनर]] कम वजन वाले नेटवर्क होते हैं, जो न्यूनतम स्पैनिंग ट्री की तरह, सभी बिंदुओं को जोड़ते हैं। इस प्रकार न्यूनतम प्रसारित हुए ट्री के विपरीत, इन सभी कनेक्टिंग पथों को छोटा होना आवश्यक है, जिनकी लंबाई उनके द्वारा जोड़े गए बिंदुओं के मध्य की दूरी के समानुपाती होती है। इस संपत्ति को प्राप्त करने के लिए, इन नेटवर्कों में सामान्यतः चक्र होते हैं और इसलिए ट्री नहीं होते हैं।{{r|eppstein}}

==गुण==

===कोण और शीर्ष डिग्री===
[[File:Kissing-3d.png|thumb|बारह इकाई गोले एक केंद्रीय इकाई क्षेत्र के सभी स्पर्शरेखा हैं। उनके 13 केंद्र बिंदुओं में से न्यूनतम प्रसारित हुए ट्री का केंद्रीय बिंदु पर डिग्री 12 है।]]जब भी यूक्लिडियन न्यूनतम प्रसारित हुए ट्री के दो किनारे एक शीर्ष पर मिलते हैं, तो उन्हें 60° या अधिक का कोण बनाना चाहिए, समानता के साथ मात्र तभी जब वे एक समबाहु त्रिभुज की दो भुजाएँ बनाते हैं। ऐसा इसलिए है, क्योंकि किसी भी तीव्र कोण बनाने वाले दो किनारों के लिए, दो किनारों में से एक को उनके द्वारा बनाए गए त्रिभुज के तीसरे, छोटे किनारे से बदला जा सकता है, जिससे छोटी कुल लंबाई वाला एक ट्री बनता है।{{r|1steiner}} इसकी तुलना में, स्टीनर ट्री की समस्या में एक मजबूत कोण सीमा होती है: इस प्रकार एक सर्वश्रेष्ठ स्टीनर ट्री के सभी कोण कम से कम 120° होते हैं।{{r|gilpol}}

वही 60° कोण सीमा चुंबन संख्या समस्या में भी होती है, यूक्लिडियन अंतरिक्ष में इकाई क्षेत्रों की अधिकतम संख्या को अन्वेषण के लिए जो किसी भी दो क्षेत्रों को प्रतिच्छेद किए बिना (स्पर्शरेखा के एक बिंदु से परे) एक केंद्रीय इकाई क्षेत्र के स्पर्शरेखा हो सकती है। इन क्षेत्रों के केंद्र बिंदुओं में एक तारे (ग्राफ सिद्धांत) के रूप में एक न्यूनतम प्रसारित हुआ ट्री होता है, जिसका केंद्रीय बिंदु अन्य सभी बिंदुओं के निकट होता है। इसके विपरीत, किसी भी शीर्ष <math>v</math> के लिए किसी भी न्यूनतम प्रसारित हुए ट्री के केंद्र में गैर-अतिव्यापी इकाई गोले का निर्माण किया जा सकता है <math>v</math> और इसके प्रत्येक किनारे के साथ बिंदुओं पर दो इकाइयां, <math>v</math> के प्रत्येक निकटतमी के लिए स्पर्शरेखा के साथ इसलिए, <math>n</math>-आयामी स्थान एक शीर्ष की अधिकतम संभव [[डिग्री (ग्राफ सिद्धांत)|डिग्री]] (इससे जुड़े प्रसारित हुए ट्री के किनारों की संख्या) में <math>n</math> आयाम में गोले की चुंबन संख्या के बराबर होती है {{r|robsal}} इस प्रकार प्लेनर न्यूनतम प्रसारित हुए ट्र की डिग्री अधिकतम छह होती है, और जब एक ट्री की डिग्री छह होती है तो सदैव अधिकतम डिग्री पांच वाला एक और न्यूनतम प्रसारित हुआ ट्री होता है।{{r|monsur}} त्रि-आयामी न्यूनतम प्रसारित हुए ट्री की डिग्री अधिकतम बारह होती है।{{r|robsal}} इस प्रकार एकमात्र उच्च आयाम जिसमें चुंबन संख्या का स्पष्ट मान ज्ञात होता है, और इस प्रकार इसमें 4, 8 और 24 आयाम होते हैं।{{r|kissing}}

किसी दिए गए निरंतर वितरण से यादृच्छिक रूप से उत्पन्न बिंदुओं के लिए, न्यूनतम स्पैनिंग ट्री [[लगभग निश्चित रूप से]] अद्वितीय होता है। किसी भी डिग्री के शीर्षों की संख्या, शीर्षों की बड़ी संख्या के लिए, शीर्षों की संख्या से लगातार गुना तक परिवर्तित हो जाती है। इस प्रकार इन स्थिरांकों का मान डिग्री और वितरण पर निर्भर करता है। चूकिं, साधारण स्थितियों के लिए भी - जैसे कि एक इकाई वर्ग में समान रूप से वितरित बिंदुओं के लिए पत्तों की संख्या -उनके स्पष्ट मान ज्ञात नहीं हैं।{{r|sse}}

===रिक्त क्षेत्र===
[[File:EMST empty regions.svg|upright=1.2|thumb|यूक्लिडियन न्यूनतम प्रसारित हुए ट्री के लिए खाली क्षेत्र: दिखाए गए लाल किनारे के लिए, इन क्षेत्रों में ट्री का कोई अन्य शीर्ष सम्मलित नहीं हो सकता है। सफेद: सापेक्ष निकटतम ग्राफ को परिभाषित करने वाला खाली लेंस। हल्का नीला: व्यास वृत्त [[गेब्रियल ग्राफ]] को परिभाषित करता है और डेलाउने त्रिकोण के लिए एक खाली वृत्त बनाता है। गहरा नीला: एक 60°-120° समचतुर्भुज जो अन्य प्रसारित हुए ट्री के किनारों के समचतुर्भुज के साथ ओवरलैप नहीं हो सकता।]]किसी भी किनारे के लिए किसी भी यूक्लिडियन न्यूनतम प्रसारित हुए ट्री का <math>uv</math>, यूवी के साथ दो वृत्तों को उनके त्रिज्या के रूप में प्रतिच्छेद करने से बना [[लेंस (ज्यामिति)|लेंस (या वेसिका पिस्किस)]] इसके आंतरिक भाग में कोई अन्य दिया गया शीर्ष <math>w</math> नहीं हो सकता है। इस प्रकार यदि किसी ट्री का किनारा <math>uv</math> है तो दूसरे प्रकार से रखें जिसके लेंस में तीसरा बिंदु <math>w</math> होता है, तो यह न्यूनतम लंबाई का नहीं होता है। क्योंकि, दो वृत्तों की ज्यामिति के अनुसार, <math>w</math> दोनों के निकट होगा <math>u</math> और <math>v</math> जितना वे एक दूसरे के प्रति निकट होते हैं। इस प्रकार अगर किनारा <math>uv</math> ट्री से हटा दिए जाए, तो <math>w</math> <math>u</math> और <math>v</math>, से किसी एक से जुड़ा रहेगा लेकिन दूसरा नहीं। हटाए गए किनारे को बदलना <math>uv</math> द्वारा <math>uw</math> या <math>vw</math> द्वारा बदला जाता है( इन दोनों किनारों में से जो भी <math>w</math> को शीर्ष पुनः जोड़ता है जहां से इसे अलग किया गया था)। इस प्रकार एक छोटा ट्री उत्पन्न होता है।{{r|gilpol}} 

किसी भी किनारे के लिए किसी भी यूक्लिडियन न्यूनतम प्रसारित हुए ट्री का <math>uv</math> 60° और 120° के कोण वाला समचतुर्भुज, जिसमें <math>uv</math> अपने लंबे विकर्ण के रूप में, यह अन्य सभी किनारों द्वारा समान रूप से निर्मित रम्बी से असंयुक्त होता है। इस प्रकार एक समापन बिंदु को साझा करने वाले दो किनारों में ओवरलैपिंग रॉम्बी नहीं हो सकती है, क्योंकि इसका मतलब 60° सेअधिक किनारे का कोण होगा, और दो असंयुक्त किनारों में ओवरलैपिंग रॉम्बी नहीं हो सकती है; यदि वे ऐसा करते, तो दोनों किनारों में से लंबे किनारे को उन्हीं चार शीर्षों के मध्य एक छोटे किनारे से बदला जा सकता है।{{r|gilpol}}

===सुपरग्राफ===
कुछ ज्यामितीय ग्राफ़ों में बिंदु समुच्चयों में खाली क्षेत्रों को सम्मलित करने वाली परिभाषाएँ होती हैं, जिससे यह पता चलता है कि उनमें हर किनारा सम्मलित है जो यूक्लिडियन न्यूनतम प्रसारित हुए ट्री का एक भाग हो सकता है। इसमे सम्मलित होते है:
*सापेक्ष निकटतम ग्राफ, जिसमें किसी भी बिंदु के जोड़े के मध्य एक किनारा होता है जब भी उनके द्वारा परिभाषित लेंस खाली होता है।
*गेब्रियल ग्राफ, जिसमें किसी भी बिंदु के जोड़े के मध्य एक किनारा होता है जब भी इस जोड़े का व्यास वाला वृत्त खाली होता है।
*डेलाउने त्रिभुज, जिसमें किसी भी बिंदु के जोड़े के मध्य एक किनारा होता है जब भी कोई खाली वृत्त उपस्थित होता है जिसमें जोड़ी एक जीवा के रूप में होती है।
*[[उर्कहार्ट ग्राफ]], प्रत्येक त्रिभुज के सबसे लंबे किनारे को हटाकर डेलाउने त्रिभुज से बनाया जाता है। प्रत्येक शेष किनारे के लिए, उस किनारे का उपयोग करने वाले डेलाउने त्रिकोण के शीर्ष सापेक्ष निकटतम ग्राफ के खाली ल्यून के भीतर नहीं हो सकते।
चूँकि इन ग्राफ़ों के लिए खाली-क्षेत्र मानदंड उत्तरोत्तर कमज़ोर होते जा रहे हैं, ये ग्राफ़ सबग्राफ़ों का एक क्रमबद्ध अनुक्रम बनाते हैं। अर्थात्, उनके किनारों के मध्य उपसमुच्चय संबंध को दर्शाने के लिए ⊆ का उपयोग करते है, इन ग्राफ़ों में निम्नलिखित संबंध होता हैं:
{{bi|left=1.6|यूक्लिडियन न्यूनतम फैले हुए पेड़ ⊆ सापेक्ष पड़ोस ग्राफ ⊆ उर्कहार्ट ग्राफ ⊆ गेब्रियल ग्राफ ⊆ डेलाउने त्रिभुज होते है।{{r|presha|comment}}}}

न्यूनतम स्पैनिंग ट्री को सम्मलित करने का अश्वासन देने वाला एक अन्य ग्राफ [[याओ ग्राफ]] होता है, जो प्रत्येक बिंदु के चारों ओर के विमान को छह 60° वेजेज में विभाजित करके और प्रत्येक वेज में प्रत्येक बिंदु को निकटतम निकटतमी से जोड़कर विमान में बिंदुओं के लिए निर्धारित किया जाता है। इस प्रकार परिणामी ग्राफ़ में सापेक्ष निकटतम ग्राफ़ सम्मलित होता है, क्योंकि खाली लेंस वाले दो कोने अपने वेजेज में एक दूसरे के निकटतम निकटतमी होते है। उपरोक्त कई अन्य ज्यामितीय ग्राफों की तरह, इस परिभाषा को उच्च आयामों के लिए सामान्यीकृत किया जा सकता है, और (डेलाउने त्रिकोण के विपरीत) इसके सामान्यीकरण में सदैव किनारों की एक रैखिक संख्या सम्मलित होती है।{{r|yao82|bwy}}

===कुल लंबाई===
<math>n</math> बिंदु के लिए इकाई वर्ग (या किसी अन्य निश्चित आकार), न्यूनतम प्रसारित हुए ट्री के किनारों की कुल लंबाई <math>O(\sqrt n)</math> होती है। बिंदुओं के कुछ समुच्चय, जैसे कि एक में समान दूरी पर स्थित बिंदु <math>\sqrt n \times \sqrt n</math> ग्रिड, इस सीमा को प्राप्त करते है।{{r|gilpol}} एक इकाई हाइपरक्यूब में अंकों के लिए <math>d</math>-आयामी स्थान, संगत सीमा<math>O(n^{(d-1)/d})</math> होती है।{{r|ss89}} यही सीमा न्यूनतम प्रसारित हुए ट्री की अपेक्षित कुल लंबाई पर भी होती है। इस प्रकार <math>n</math> एक इकाई वर्ग या इकाई हाइपरक्यूब से समान रूप से और स्वतंत्र रूप से चुने गए बिंदु होते है।{{r|steele}} इकाई वर्ग पर लौटने पर, न्यूनतम प्रसारित हुए ट्री के वर्ग किनारे की लंबाई का योग <math>O(1)</math> होता है। यह सीमा इस अवलोकन से मिलती है कि किनारों में असंयुक्त रम्बी है, जिसका क्षेत्रफल किनारे की लंबाई के वर्ग के समानुपाती होता है। <math>O(\sqrt n)</math> कुल लंबाई पर बाध्य कॉची-श्वार्ज़ असमानता के अनुप्रयोग द्वारा अनुसरण किया जाता है।{{r|gilpol}}

इन परिणामों की एक और व्याख्या यह है कि एक इकाई वर्ग में बिंदुओं के किसी भी समुच्चय के लिए औसत किनारे की लंबाई <math>O(1/\sqrt n)</math> होती है, नियमित ग्रिड में बिंदुओं के अंतर के अधिकतम आनुपातिक; और एक इकाई वर्ग में यादृच्छिक बिंदुओं के लिए औसत लंबाई <math>1/\sqrt n</math> आनुपातिक होती है। चूकिं, यादृच्छिक स्थितियों में, उच्च संभावना के साथ सबसे लंबे किनारे की लंबाई लगभग होती है:<math display=block>\sqrt{\frac{\log n}{\pi n}},</math>इस प्रकार यह क गैर-स्थिर कारक द्वारा औसत से अधिक लंबा होता है। उच्च संभावना के साथ, सबसे लंबा किनारा प्रसारित हुए ट्री का एक पत्ता बनाता है, और अन्य सभी बिंदुओं से दूर एक बिंदु को उसके निकटतम निकटतमी से जोड़ता है। इस प्रकार बड़ी संख्या में अंकों के लिए, इसके अपेक्षित मूल्य के आसपास सबसे लंबी किनारे की लंबाई का वितरण [[लाप्लास वितरण]] में परिवर्तित हो जाता है।{{r|penrose}}कोई भी ज्यामितीय स्पैनर, एक पूर्ण ज्यामितीय ग्राफ का एक उपग्राफ जिसकी सबसे छोटी पथ समस्या यूक्लिडियन दूरी का अनुमान लगाती है, उसकी कुल किनारे की लंबाई कम से कम न्यूनतम प्रसारित हुए ट्री जितनी बड़ी होनी चाहिए, और एक ज्यामितीय स्पैनर के लिए मानक गुणवत्ता उपायों में से एक इसकी कुल लंबाई और समान बिंदुओं के लिए न्यूनतम प्रसारित हुए ट्री के मध्य का अनुपात इसकी होता है। इस प्रकार स्पैनर के निर्माण की कई विधियाँ होती है ,जैसे कि [[लालची ज्यामितीय स्पैनर|ग्रीडी ज्यामितीय स्पैनर]], इस अनुपात के लिए एक स्थिर सीमा प्राप्त करती हैं।{{r|eppstein}} यह अनुमान लगाया गया है कि स्टीनर अनुपात, विमान में बिंदुओं के समान समुच्चय के लिए न्यूनतम प्रसारित हुए ट्री और स्टीनर ट्री की कुल लंबाई के मध्य सबसे बड़ा संभव अनुपात होता है। <math>2/\sqrt{3}\approx 1.1547</math>, एक समबाहु त्रिभुज में तीन बिंदुओं का अनुपात होता है।{{r|gilpol}} 

===उपखंड===
यदि यूक्लिडियन न्यूनतम प्रसारित हुए ट्री के प्रत्येक किनारे को उसके मध्य बिंदु पर एक नया बिंदु जोड़कर उप-विभाजित किया जाता है, तो परिणामी ट्री अभी भी संवर्धित बिंदु समुच्चय का न्यूनतम प्रसारित हुआ ट्री होता है। इस उपविभाजन प्रक्रिया को दोहराने से यूक्लिडियन न्यूनतम प्रसारित हुए ट्री को इच्छानुसार ढंग से सूक्ष्मता से उपविभाजित किया जा सकता है। यघपि, मात्र कुछ किनारों को उप-विभाजित करना, या किनारों को मध्यबिंदु के अतिरिक्त अन्य बिंदुओं पर उप-विभाजित करना, एक बिंदु समुच्चय उत्पन्न कर सकता है जिसके लिए उप-विभाजित ट्री न्यूनतम प्रसारित हुए ट्री नहीं होते है।{{r|bgj78}}

==कम्प्यूटेशनल जटिलता==
<math>O(n^2)</math> बिंदुओं के प्रत्येक जोड़े के मध्य एक किनारे के साथ एक पूर्ण ग्राफ़ का निर्माण करके, यूक्लिडियन दूरी के आधार पर, और फिर उस पर प्राइम के कलन विधि जैसे ग्राफ़ न्यूनतम स्पैनिंग ट्री कलन विधि को प्रयुक्त करके किसी भी आयाम में बिंदुओं के लिए, समय में न्यूनतम प्रसारित हुए ट्री का निर्माण किया जा सकता है। इस प्रकार इन कलन विधि को पूर्ण ग्राफ़ पर समय <math>O(n^2)</math> लेने के लिए बनाया जा सकता है, एक अन्य सामान्य विकल्प के विपरीत, क्रुस्कल का कलन विधि, जो धीमा होता है क्योंकि इसमें सभी दूरियों को क्रमबद्ध में सम्मलित करना होता है।{{r|eppstein}} निम्न-आयामी स्थानों में बिंदुओं के लिए, समस्या को अधिक शीघ्रता से हल किया जा सकता है, जैसा कि नीचे बताया गया है।

यूक्लिडियन दूरियों की गणना में [[वर्गमूल]] गणना सम्मलित होती है। किनारे के वजन की किसी भी तुलना में, दूरियों के अतिरिक्यत यूक्लिडियन दूरियों के वर्गों की तुलना करने से समान क्रम प्राप्त होता है, और इसलिए ट्री की अन्य गणना में कोई बदलाव नहीं होता है। इस प्रकार यह लघु गणना को गति देता है और मात्र पूर्णांक अंकगणित का उपयोग करके पूर्णांक निर्देशांक वाले बिंदुओं के लिए न्यूनतम स्पैनिंग ट्री का निर्माण करने की अनुमति देता है।{{r|yao82}}

===दो आयाम===
समतल बिंदुओं के न्यूनतम प्रसारित हुए ट्री के अन्वेषण के लिए एक उच्च दृष्टिकोण इस गुण का उपयोग करता है कि यह डेलाउने त्रिकोण का एक उपसमूह होता है:
# डेलाउने त्रिभुज की गणना करें, जिसे किया <math>O(n\log n)</math> समय में जा सकता है। क्योंकि डेलाउने त्रिभुज एक [[समतलीय ग्राफ]] होता है, इसमें अधिकतम <math>3n-6</math> किनारे होते है। 
# प्रत्येक किनारे को उसकी (वर्गीकृत) लंबाई के साथ लेबल करें।
# एक ग्राफ़ न्यूनतम स्पैनिंग ट्री कलन विधि चलाएँ। क्योंकि वहां <math>O(n)</math> किनरे होते है, किसी भी मानक न्यूनतम स्पैनिंग ट्री कलन विधि का उपयोग द्वारा समय <math>O(n\log n)</math> की इसको आवश्यकता होती है।
परिणाम एक कलन विधि  <math>O(n\log n)</math> समय लेता है,{{r|shahoe}} गणना के कुछ प्रारू में सर्वश्रेष्ठ निम्नलिखित दिए गये है (निचली सीमा देखें)।

यदि इनपुट निर्देशांक पूर्णांक होता हैं और उन्हें [[सरणी सूचकांक]] के रूप में उपयोग किया जा सकता है, तो उच्च कलन विधि संभव होता हैं: डेलाउने त्रिकोण का निर्माण [[यादृच्छिक एल्गोरिदम|यादृच्छिक कलन विधि]] द्वारा अपेक्षित समय <math>O(n\log\log n)</math> में किया जा सकता है।{{r|bm09}} इसके अतिरिक्त, चूंकि डेलाउने त्रिकोण एक समतलीय ग्राफ होता है, इसलिए इसके न्यूनतम प्रसारित हुए ट्री को बोरोव्का के कलन विधि के एक प्रकार द्वारा [[रैखिक समय]] में पाया जा सकता है जो कलन विधि के प्रत्येक चरण के बाद घटकों की प्रत्येक जोड़ी के मध्य सबसे सस्ते किनारे को छोड़कर सभी को हटा देता है।{{r|eppstein|mares}} इसलिए, इस कलन विधि के लिए कुल अपेक्षित समय <math>O(n\log\log n)</math>होता है।{{r|bm09}} इस प्रकार दूसरी दिशा में, डेलाउने त्रिकोण का निर्माण निकट-रेखीय समय सीमा <math>O(n\log^* n)</math> में न्यूनतम प्रसारित हुए ट्री से किया जा सकता है, जहाँ <math>\log^*</math> [[पुनरावृत्त लघुगणक]] को प्रदर्शित करता है।{{r|devillers}}

===उच्च आयाम===
समस्या का सामान्यीकरण <math>n</math> में अंक <math>d</math>-आयामी स्थान <math>\R^d</math>में भी किया जा सकता है। उच्च आयामों में, कनेक्टिविटी डेलाउने त्रिकोण द्वारा निर्धारित की जाती है (जो, इसी तरह, उत्तल पतवार को <math>d</math>-डायमेंशनल [[संकेतन]] में विभाजित करती है) इसमें कुछ न्यूनतम प्रसारित हुए ट्री सम्मलित होते हैं; यघपि, त्रिभुज में पूरा ग्राफ़ सम्मलित हो सकता है।{{r|aesw}} इसलिए, यूक्लिडियन न्यूनतम प्रसारित हुए ट्री को पूर्ण ग्राफ़ के प्रसारित हुए ट्री के रूप में या डेलाउने त्रिकोण के प्रसारित हुए ट्री के रूप में अन्वेषण के लिए दोनों <math>O(dn^2)</math> समय लेते है। इस प्रकार तीन आयामों के लिए न्यूनतम प्रसारित हुए ट्री को समय <math>O\bigl((n\log n)^{4/3}\bigr)</math>में पाया जा सकता है, और किसी भी बड़े आयाम को, प्रदर्शित किये गये समय में पाया जा सकता है: <math display=block>O\left(n^{2-\frac{2}{\lceil d/2\rceil+1}+\varepsilon}\right)</math>किसी के लिए <math>\varepsilon>0</math>- संपूर्ण ग्राफ़ औलेकिनउने त्रिभुज कलन विधि के लिए द्विघात समय सीमा से अधिक शीघ्र होता है।{{r|aesw}}

उच्च-आयामी न्यूनतम प्रसारित हुए ट्री के लिए सर्वश्रेष्ठ समय जटिलता अज्ञात बनी हुई है,{{r|topp}} परन्तु यह द्विवर्णीय निकटतम युग्मों की गणना की जटिलता से निकटता से संबंधित है।इस प्रकार द्विवर्णी निकटतम जोड़ी समस्या में, इनपुट बिंदुओं का एक समुच्चय होता है, जिसे दो अलग-अलग रंग दिए गए हैं (जैसे, लाल और नीला)। आउटपुट न्यूनतम संभव दूरी के साथ एक लाल बिंदु और एक नीले बिंदु की एक जोड़ी होती है। यह जोड़ी सदैव न्यूनतम प्रसारित हुए ट्री में किनारों में से एक बनाती है। इसलिए, बाइक्रोमैटिक निकटतम जोड़ी समस्या को न्यूनतम प्रसारित हुए ट्री के निर्माण और सबसे छोटे लाल-नीले किनारे के लिए इसके किनारों को स्कैन करने में लगने वाले समय में हल किया जा सकता है। इसके विपरीत, किसी दिए गए बिंदुओं के समुच्चय के किसी भी उपसमूह के लाल-नीले रंग के लिए, बाइक्रोमैटिक निकटतम जोड़ी उपसमूह के न्यूनतम प्रसारित हुए ट्री के एक किनारे का उत्पादन करती है। इस प्रकार उपसमुच्चय के रंगों के क्रम को सावधानीपूर्वक चुनकर, और प्रत्येक उपसमस्या के द्विवर्णीय निकटतम जोड़े को ढूंढकर, समान संख्या में बिंदुओं के लिए द्विवर्णीय निकटतम जोड़े के अन्वेषण के लिए सर्वश्रेष्ठ समय के आनुपातिक समय में न्यूनतम प्रसारित हुए ट्री को पाया जा सकता है, चाहे वह सर्वश्रेष्ठ समय कुछ भी हो।{{r|aesw|kln}}

किसी भी सीमित आयाम में समान रूप से यादृच्छिक बिंदु समुच्चय के लिए, याओ ग्राफ{{r|yao82}} या डेलाउने त्रिकोण में किनारों की रैखिक अपेक्षित संख्या होती है, इसमें न्यूनतम प्रसारित हुए ट्री होने की गारंटी होती है, और रैखिक अपेक्षित समय में इसका निर्माण किया जा सकता है।{{r|bwy|clarkson|dwyer}} इन ग्राफ़ों से, [[अपेक्षित रैखिक समय एमएसटी एल्गोरिदम|अपेक्षित रैखिक समय एमएसटी कलन विधि]] का उपयोग करके, न्यूनतम स्पैनिंग ट्री का निर्माण रैखिक समय में किया जा सकता है।{{r|kkt}} चूकिं, क्लस्टर्ड डेटा से आने वाले इनपुट पर इन तरीकों केव्यर्थ प्रदर्शन ने [[एल्गोरिथम इंजीनियरिंग|कलन विधि इंजीनियरिंग]] शोधकर्ताओं को कुछ हद तक धीमी गति से प्रकार विकसित करने के लिए प्रेरित किया है यादृच्छिक इनपुट या इनपुट के लिए <math>O(n\log n)</math>समयबद्ध, जिनकी दूरी और क्लस्टरिंग यादृच्छिक डेटा के समान होती है, जबकि वास्तविक दुनिया डेटा पर उच्चतम प्रदर्शन प्रदर्शित करती है।{{r|nzz|cck|mrg}}

एक अच्छी तरह से अलग किया गया जोड़ी अपघटन दिए गए बिंदुओं के उपसमुच्चय के जोड़े का एक परिवार होता है, जिससे प्रत्येक जोड़ी अंक उपसमुच्चय के इन जोड़े में से एक से संबंधित होती है, और जिससे उपसमुच्चय की एक ही जोड़ी से आने वाले बिंदुओं के सभी जोड़े लगभग एक ही लंबाई के होते है। <math>O(n\log n)</math>समय में उपसमुच्चय की एक रैखिक संख्या और प्रत्येक उपसमुच्चय के लिए बिंदुओं की एक प्रतिनिधि जोड़ी के साथ एक अच्छी तरह से अलग की गई जोड़ी का अपघटन अन्वेषण करना संभव होता है। इस प्रकार इन प्रतिनिधि जोड़ियों द्वारा बनाए गए ग्राफ़ का न्यूनतम स्पैनिंग ट्री न्यूनतम स्पैनिंग ट्री का एक अनुमानित मान होता है। इन विचारों का उपयोग करते हुए, एक <math>(1+\varepsilon)</math>-न्यूनतम प्रसारित हुए ट्री का अनुमानित मान <math>O(n\log n)</math> समय में नियतांक <math>\varepsilon</math> के लिए पाया जा सकता है। अधिक स्पष्ट रूप से, प्रत्येक प्रतिनिधि जोड़ी को उसके समकक्ष वर्ग में निकटतम जोड़ी का अनुमान लगाने के लिए चुनकर, और विभिन्न जोड़ियों के लिए इस सन्निकटन की गुणवत्ता को ध्यान से अलग करके, <math>\varepsilon</math> पर निर्भरता <math>O(n \log n + (\varepsilon^{-2} \log ^2 \tfrac{1}{\varepsilon})n)</math>समय सीमा में किसी भी निश्चित आयाम के लिए इस प्रकार दिया जा सकता है।{{r|arymou}}

===गतिशील और गतिज(काइनेटिक)===
यूक्लिडियन न्यूनतम प्रसारित हुए ट्री को चलती या बदलते बिंदुओं की प्रणालियों के लिए कई अलग-अलग ढंग से सामान्यीकृत किया गया है:
*यदि बिंदुओं का एक समुच्चय गतिशील सम्मिलन या बिंदुओं के विलोपन के अनुक्रम से होकर निकलता है, तो इनमें से प्रत्येक अद्यतन बिंदुओं के न्यूनतम प्रसारित हुए ट्री में परिवर्तन की एक सीमित मात्रा को प्रेरित करता है। इस प्रकार जब अद्यतन अनुक्रम पहले से ज्ञात होता है, तो विमान में बिंदुओं के लिए, प्रत्येक प्रविष्टि या विलोपन के बाद परिवर्तन समय <math>O(\log^2 n)</math>पर पाया जा सकता है। {{r|offline}} जब अद्यतनों को [[ ऑनलाइन एल्गोरिदम |ऑनलाइन कलन विधि]] प्रकार से पलेकिनत किया जाता है, तो धीमी (परन्तु फिर भी बहु-लघुगणकीय) <math>O(\log^{10} n)</math> समयबद्धता ज्ञात होती है।{{r|chadyn}} इस प्रकार समस्या के उच्च-आयामी संस्करणों के लिए प्रति अद्यतन समय धीमा होता है, परन्तु फिर भी अधरेखीय होता है।{{r|extrema}}
*<math>n</math> स्थिर गति के लिए एक साथ, या अधिक सामान्य बीजगणितीय गति के साथ रैखिक रूप से आगे बढ़ने वाले बिंदु, न्यूनतम प्रसारित हुए ट्री स्वैप के अनुक्रम से बदल जाएंगे, जिसमें एक किनारा हटा दिया जाता है और दूसरा इसे उस समय में बदल देता है जहां दोनों की लंबाई समान होती है।{{r|kti}} इस प्रकार रैखिक गतियों के लिए, परिवर्तनों की संख्या अधिक से अधिक <math>n^{25/9}</math> से थोड़ी अधिक होती है।{{r|chalev}} अधिक सामान्य बीजगणितीय गतियों के लिए, डेवनपोर्ट-शिन्ज़ेल अनुक्रमों के सिद्धांत के आधार पर, स्वैप की संख्या पर एक निकट-घन ऊपरी सीमा होती है।{{r|rzcomb}}
*न्यूनतम गतिमान स्पैनिंग ट्री समस्या फिर से समय के अंतराल पर निरंतर गति के साथ रैखिक रूप से आगे बढ़ने वाले बिन्दुओं से संबंधित होती है, और एक ऐसे ट्री की खोज करती है जो इस अंतराल के समय किसी भी क्षण होने वाले वजन के अधिकतम योग को कम कर दे। त्रुटिहीन गणना करना एनपी-कठिन होता है, परन्तु बहुपद समय में दो के कारक के भीतर इसका अनुमान लगाया जा सकता है।{{r|abb}}
*[[गतिज यूक्लिडियन न्यूनतम फैले हुए पेड़|गतिज यूक्लिडियन न्यूनतम प्रसारित हुए ट्री]] समस्या एक [[गतिज डेटा संरचना]] की मांग करती है जो न्यूनतम स्पैनिंग ट्री को बनाए रख सके क्योंकि इसके बिंदु निरंतर गति और सम्मिलन और विलोपन दोनों से गुजरते हैं। इस प्रकार कई पत्रों ने ऐसी संरचनाओं का अध्ययन किया है,{{r|bgz|aegh|rzkin|rakwz|msvw}} और जो लगभग घन-कुल समय के साथ बीजगणितीय रूप से गतिशील बिंदुओं के लिए एक गतिज संरचना ज्ञात होती है, जो स्वैप की संख्या की सीमा से लगभग समान होती है।{{r|rakwz}}

===निचली सीमा===
स्पर्शोन्मुख निचली सीमा <math>\Omega(n\log n)</math> यूक्लिडियन न्यूनतम प्रसारित हुए ट्री की समस्या को गणना के प्रतिबंधित प्रारूप में स्थापित किया जा सकता है। इनमें [[बीजगणितीय निर्णय वृक्ष|बीजगणितीय निर्णय ट्री]] और [[बीजगणितीय संगणना वृक्ष|बीजगणितीय संगणना ट्री]] प्रारूप सम्मलित होता हैं, जिसमें कलन विधि को मात्र कुछ प्रतिबंधित प्राइमेटिव्स के माध्यम से इनपुट बिंदुओं तक पहुंच होती है जो उनके निर्देशांक पर सरल बीजगणितीय गणना करते हैं। इस प्रकार इन प्रारूप में, अंक समस्या की निकटतम जोड़ी की आवश्यकता होती है, परन्तु निकटतम जोड़ी आवश्यक रूप से न्यूनतम प्रसारित हुए ट्री का एक किनारा होता है, इसलिए न्यूनतम प्रसारित हुए ट्री कोभी इतने समय <math>\Omega(n\log n)</math>की आवश्यकता होती है। इसलिए, समय में समतल न्यूनतम प्रसारित हुए ट्री के निर्माण के लिए कलन विधि <math>O(n\log n)</math> इस प्रारूप के भीतर, उदाहरण के लिए डेलाउने त्रिभुज का उपयोग करके, सर्वश्रेष्ठ होते हैं।{{r|yao89}} यघपि, ये निचली सीमाएँ पूर्णांक बिंदु निर्देशांक के साथ गणना के प्रारूप पर लागू नहीं होती हैं, जिसमें उन निर्देशांक पर बिटवाइज़ संचालन और [[रैंडम एक्सेस]] संचालन की अनुमति प्राप्त होती है। इस प्रकार इन प्रारूपो में, तेज़ कलन विधि संभव होता हैं, जैसा कि ऊपर बताया गया है।{{r|bm09}}

== अनुप्रयोग ==
यूक्लिडियन न्यूनतम प्रसारित ट्री का एक स्पष्ट अनुप्रयोग स्थानों के एक समुच्चय को जोड़ने के लिए तारों या पाइपों का सबसे सस्ता नेटवर्क ढूंढता है, यह मानते हुए कि लिंक की प्रति यूनिट लंबाई एक निश्चित राशि खर्च होती है। न्यूनतम प्रसारित ट्री पर पहला प्रकाशन सामान्यतः समस्या के भौगोलिक संस्करण से संबंधित था, जिसमें [[दक्षिण मोरावियन क्षेत्र]] के लिए [[विद्युत ग्रिड]] का डिज़ाइन सम्मलित था,{{r|history}} और परिपथ में तार की लंबाई को कम करने के लिए एक एप्लिकेशन का वर्णन 1957 में लोबरमैन और वेनबर्गर द्वारा किया गया था।{{r|lobwei}}

न्यूनतम प्रसारित हुए ट्री एकल-लिंकेज क्लस्टरिंग से निकटता से संबंधित होते हैं, जो [[पदानुक्रमित क्लस्टरिंग]] के कई विधियों में से एक होता है। इस प्रकार न्यूनतम प्रसारित हुए ट्री के किनारे, उनकी लंबाई के अनुसार क्रमबद्ध, इस क्लस्टरिंग विधि में समूहों को बड़े समूहों में विलय करने का क्रम देते हैं। एक बार जब ये किनारे मिल जाते हैं, तो किसी भी कलन विधि द्वारा, उनका उपयोग <math>O(n\log n)</math> समय में [[सिंगल-लिंकेज क्लस्टरिंग]] के निर्माण के लिए किया जा सकता है।{{r|gowros}} चूकिं सिंगल-लिंकेज क्लस्टरिंग द्वारा निर्मित लंबे पतले क्लस्टर आकार कुछ प्रकार के डेटा, जैसे कि [[ मिश्रण मॉडल |मिश्रण प्रारूप]] , के लिए व्यर्थ हो सकते हैं, यह उन अनुप्रयोगों में एक अच्छा विकल्प हो सकता है जहां क्लस्टर से स्वयं लंबे पतले आकार की उम्मीद की जाती है, जैसे कि आकाशगंगाओं के काले पदार्थ के प्रभामंडल का प्रारूप करना होता है।{{r|mrg}} इस प्रकार [[भौगोलिक सूचना विज्ञान]] में, कई शोधकर्ता समूहों ने भवन के सार्थक समूहों की पहचान करने के लिए भवनों के केंद्रक के न्यूनतम प्रसारित हुए ट्री का उपयोग किया है, उदाहरण के लिए किसी अन्य प्रकार से असंगत के रूप में पहचाने गए किनारों को हटाकर किया था।{{r|urban}}

विमान में वक्रों के आकार का अनुमान लगाने के लिए न्यूनतम प्रसारित हुए ट्री का भी उपयोग किया जाता है, वक्र के साथ दिए गए बिंदु दिए गए हैं। इस प्रकार एक चिकने वक्र के लिए, उसके स्थानीय फीचर आकार की तुलना में अधिक ध्यानपूर्वक प्रतिरूप लिया जाता है, न्यूनतम प्रसारित हुआ ट्री वक्र के साथ लगातार बिंदुओं को जोड़ने वाला एक पथ बनाएगा। अधिक सामान्रयतः, समान विधियां एकल जुड़े हुए समुच्चय के अतिरिक्त बिंदीदार या धराशायी शैली में खींचे गए वक्रों को पहचान सकती हैं। इस वक्र-अन्वेषण तकनीक के अनुप्रयोगों में [[बुलबुला कक्ष|बुदबुदा कक्ष]] (बबल चैम्मबर) कणों द्वारा छोड़े गए ट्रैक की स्वचालित रूप से पहचान करने में [[कण भौतिकी]] सम्मलित होता है।{{r|zahn}} इस विचार के अधिक परिष्कृत संस्करण, गतिशील न्यूनतम वर्ग विधि का मार्गदर्शन करने के लिए प्रसारित हुए ट्री की टोपोलॉजी का उपयोग करके, ध्वनि वाले बिंदुओं के एक क्लाउड से वक्र पा सकते हैं जो सामान्यतः वक्र रूपरेखा का अनुसरण करते हैं।{{r|lee}}

न्यूनतम प्रसारित हुए ट्री का एक अन्य अनुप्रयोग [[यूक्लिडियन ट्रैवलिंग सेल्समैन समस्या]] के लिए एक निरंतर-कारक सन्निकटन कलन विधि होती है, जो एक बिंदु समुच्चय के सबसे छोटे [[बहुभुजीकरण]] अन्वेषण की समस्या होती है। इस प्रकार न्यूनतम प्रसारित हुए ट्री की सीमा के चारों ओर घूमना सर्वश्रेष्ठ लंबाई के दो के कारक के भीतर सर्वश्रेष्ठ ट्रैवलिंग सेल्समैन टूर का अनुमान लगा सकता है।{{r|shahoe}} चूकिं, अधिक स्पष्ट [[बहुपद समय सन्निकटन योजना]] इस समस्या के लिए जानी जाती हैं।{{r|bargot}} [[वायरलेस तदर्थ नेटवर्क]] में, न्यूनतम प्रसारित हुए ट्री में पथों के साथ [[प्रसारण (नेटवर्किंग)]] संदेश न्यूनतम-ऊर्जा प्रसारण रूटिंग का स्पष्ट अनुमान हो सकता है, जिसकी पुनः त्रुटिहीन गणना करना कठिन होता है।{{r|wclf|chrvp|fknp|ambuhl}}

==प्रतीति==
यूक्लिडियन न्यूनतम प्रसारित हुए ट्री के लिए प्राप्ति की समस्या इनपुट के रूप में एक अमूर्त ट्री (ग्राफ सिद्धांत) लेती है और ट्री के प्रत्येक शीर्ष (कुछ निश्चित आयाम के स्थान में) के लिए एक ज्यामितीय स्थान की जाँच करती है, जैसे कि दिया गया ट्री न्यूनतम प्रसारित हुए ट्री के बराबर होता है। प्रत्येक अमूर्त ट्री को ऐसी अनुभूति नहीं होती; उदाहरण के लिए, ट्री को प्रत्येक शीर्ष की डिग्री पर बंधी चुंबन संख्या का पालन करना होता है। इस प्रकार अतिरिक्त प्रतिबंध उपस्थित होता हैं; उदाहरण के लिए, एक समतल न्यूनतम प्रसारित हुए ट्री के लिए यह संभव नहीं है कि उसका डिग्री-छह का शीर्ष पांच या छह डिग्री के शीर्ष के निकट हो।{{r|monsur}} यह निर्धारित करना कि क्या द्वि-आयामी अनुभूति उपस्थित है, एनपी-कठोर होता है। यघपि, कठोरता का प्रमाण इस तथ्य पर निर्भर करता है कि एक ट्री में डिग्री-छह शीर्षों में प्रतीति का एक बहुत ही सीमित समुच्चय होता है: ऐसे शीर्ष के निकटतमियों को उस शीर्ष पर केंद्रित एक नियमित षट्भुज के शीर्ष पर रखा जाना चाहिए।{{r|ew94}} इस प्रकार अधिकतम डिग्री पांच के ट्री के लिए, एक समतलीय प्रतीति सदैव उपस्थित रहता है।{{r|monsur}} इसी तरह, अधिकतम डिग्री दस के ट्री के लिए, एक त्रि-आयामी अनुभूति सदैव उपस्थित रहती है।{{r|king}} इन प्रतीति के लिए, कुछ ट्री को उनके सबसे छोटे किनारे की लंबाई के सापेक्ष घातीय लंबाई के किनारों और घातीय क्षेत्र के बाउंडिंग बॉक्स की आवश्यकता हो सकती है।{{r|abcfks}} अधिकतम डिग्री चार के ट्री में छोटे समतलीय प्रतीति होते हैं, जिनमें बहुपद रूप से बंधे किनारे की लंबाई और सीमांकित डिब्बे होते हैं।{{r|frakau}}

==यह भी देखें==
*सरलरेखीय न्यूनतम स्पैनिंग ट्री, [[टैक्सीकैब ज्यामिति]] का उपयोग करके मापी गई दूरियों वाला एक न्यूनतम स्पैनिंग ट्री होता है। 

== संदर्भ ==
{{reflist|refs=

<ref name=1steiner>{{citation
 | last1 = Georgakopoulos | first1 = George
 | last2 = Papadimitriou | first2 = Christos H. | author2-link = Christos Papadimitriou
 | doi = 10.1016/0196-6774(87)90032-0
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 875330
 | pages = 122–130
 | title = The 1-Steiner tree problem
 | volume = 8
 | year = 1987}}</ref>

<ref name=abb>{{citation
 | last1 = Akitaya | first1 = Hugo A.
 | last2 = Biniaz | first2 = Ahmad
 | last3 = Bose | first3 = Prosenjit | author3-link = Jit Bose
 | last4 = De Carufel | first4 = Jean-Lou
 | last5 = Maheshwari | first5 = Anil
 | last6 = da Silveira | first6 = Luís Fernando Schultz Xavier
 | last7 = Smid | first7 = Michiel
 | editor1-last = Lubiw | editor1-first = Anna | editor1-link = Anna Lubiw
 | editor2-last = Salavatipour | editor2-first = Mohammad R.
 | contribution = The minimum moving spanning tree problem
 | doi = 10.1007/978-3-030-83508-8_2
 | pages = 15–28
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings
 | volume = 12808
 | year = 2021| s2cid = 234599877
 }}</ref>

<ref name=abcfks>{{citation
 | last1 = Angelini | first1 = Patrizio
 | last2 = Bruckdorfer | first2 = Till
 | last3 = Chiesa | first3 = Marco
 | last4 = Frati | first4 = Fabrizio
 | last5 = Kaufmann | first5 = Michael
 | last6 = Squarcella | first6 = Claudio
 | doi = 10.1016/j.comgeo.2012.10.011
 | issue = 2, part B
 | journal = [[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]
 | mr = 3123788
 | pages = 200–213
 | title = On the area requirements of Euclidean minimum spanning trees
 | volume = 47
 | year = 2014| doi-access = free
 }}</ref>

<ref name=aegh>{{citation
 | last1 = Agarwal | first1 = Pankaj K. | author1-link = Pankaj K. Agarwal
 | last2 = Eppstein | first2 = David | author2-link = David Eppstein
 | last3 = Guibas | first3 = Leonidas J. | author3-link = Leonidas J. Guibas
 | last4 = Henzinger | first4 = Monika Rauch | author4-link = Monika Henzinger
 | contribution = Parametric and Kinetic Minimum Spanning Trees
 | doi = 10.1109/SFCS.1998.743510
 | pages = 596–605
 | publisher = IEEE Computer Society
 | title = 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8–11, 1998, Palo Alto, California, USA
 | year = 1998| s2cid = 2559456 | url = https://infoscience.epfl.ch/record/99344/files/AgarwalEGH98.pdf }}</ref>

<ref name=aesw>{{citation
 | last1 = Agarwal | first1 = P. K. | author1-link = Pankaj K. Agarwal
 | last2 = Edelsbrunner | first2 = H. | author2-link = Herbert Edelsbrunner
 | last3 = Schwarzkopf | first3 = O. | author3-link = Otfried Cheong
 | last4 = Welzl | first4 = E. | author4-link = Emo Welzl
 | doi = 10.1007/BF02574698 | doi-access = free
 | issue = 1
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1115099
 | pages = 407–422
 | publisher = Springer
 | title = Euclidean minimum spanning trees and bichromatic closest pairs
 | volume = 6
 | year = 1991}}</ref>

<ref name=ambuhl>{{citation
 | last = Ambühl | first = Christoph
 | editor1-last = Caires | editor1-first = Luís
 | editor2-last = Italiano | editor2-first = Giuseppe F. | editor2-link = Giuseppe F. Italiano
 | editor3-last = Monteiro | editor3-first = Luís
 | editor4-last = Palamidessi | editor4-first = Catuscia | editor4-link = Catuscia Palamidessi
 | editor5-last = Yung | editor5-first = Moti
 | contribution = An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks
 | doi = 10.1007/11523468_92
 | pages = 1139–1150
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings
 | volume = 3580
 | year = 2005}}</ref>

<ref name=arymou>{{citation
 | last1 = Arya | first1 = Sunil
 | last2 = Mount | first2 = David M. | author2-link = David Mount
 | editor-last = Krauthgamer | editor-first = Robert
 | contribution = A fast and simple algorithm for computing approximate Euclidean minimum spanning trees
 | doi = 10.1137/1.9781611974331.ch85
 | mr = 3478461
 | pages = 1220–1233
 | title = Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016
 | year = 2016| doi-access = free
 }}</ref>

<ref name=bargot>{{citation
 | last1 = Bartal | first1 = Yair
 | last2 = Gottlieb | first2 = Lee-Ad
 | contribution = A linear time approximation scheme for Euclidean TSP
 | doi = 10.1109/FOCS.2013.80
 | mr = 3246273
 | pages = 698–706
 | title = 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA
 | year = 2013| s2cid = 17514182
 }}</ref>

<ref name=bdek>{{citation
 | last1 = Bose | first1 = Prosenjit | author1-link = Jit Bose
 | last2 = Devroye | first2 = Luc | author2-link = Luc Devroye
 | last3 = Evans | first3 = William
 | last4 = Kirkpatrick | first4 = David | author4-link = David G. Kirkpatrick
 | doi = 10.1137/S0895480197318088
 | issue = 2
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 2257270
 | pages = 412–427
 | title = On the spanning ratio of Gabriel graphs and β-skeletons
 | volume = 20
 | year = 2006}}</ref>

<ref name=bgj78>{{citation
 | last1 = Boyce | first1 = W. M.
 | last2 = Garey | first2 = M. R. | author2-link = Michael Garey
 | last3 = Johnson | first3 = D. S. | author3-link = David S. Johnson
 | doi = 10.1002/net.3230080302
 | issue = 3
 | journal = Networks
 | mr = 491324
 | pages = 187–192
 | title = A note on bisecting minimum spanning trees
 | volume = 8
 | year = 1978}}</ref>

<ref name=bgz>{{citation
 | last1 = Basch | first1 = Julien
 | last2 = Guibas | first2 = Leonidas J. | author2-link = Leonidas J. Guibas
 | last3 = Zhang | first3 = Li
 | editor-last = Boissonnat | editor-first = Jean-Daniel | editor-link = Jean-Daniel Boissonnat
 | contribution = Proximity problems on moving points
 | doi = 10.1145/262839.262998
 | pages = 344–351
 | publisher = Association for Computing Machinery
 | title = Proceedings of the Thirteenth Annual Symposium on Computational Geometry, Nice, France, June 4–6, 1997
 | year = 1997| s2cid = 15556637
 | doi-access = free
 }}</ref>

<ref name=bm09>{{citation
 | last1 = Buchin | first1 = Kevin
 | last2 = Mulzer | first2 = Wolfgang
 | doi = 10.1145/1944345.1944347
 | issue = 2
 | journal = [[Journal of the ACM]]
 | mr = 2786587
 | page = A6:1–A6:27
 | title = Delaunay triangulations in {{mvar|O}}(sort({{mvar|n}})) time and more
 | volume = 58
 | year = 2011| s2cid = 11316974
 }}</ref>

<ref name=bwy>{{citation
 | last1 = Bentley | first1 = Jon Louis | author1-link = Jon Bentley (computer scientist)
 | last2 = Weide | first2 = Bruce W.
 | last3 = Yao | first3 = Andrew C. | author3-link = Andrew Yao
 | doi = 10.1145/355921.355927
 | issue = 4
 | journal = [[ACM Transactions on Mathematical Software]]
 | mr = 599977
 | pages = 563–580
 | title = Optimal expected-time algorithms for closest point problems
 | volume = 6
 | year = 1980| s2cid = 17238717 | url = https://figshare.com/articles/journal_contribution/6608108 }}</ref>

<ref name=cck>{{citation
 | last1 = Chatterjee | first1 = S.
 | last2 = Connor | first2 = M.
 | last3 = Kumar | first3 = P.
 | editor-last = Festa | editor-first = Paola
 | contribution = Geometric minimum spanning trees with GeoFilterKruskal
 | doi = 10.1007/978-3-642-13193-6_41
 | pages = 486–500
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title =  Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010, Proceedings
 | volume = 6049
 | year = 2010}}</ref>

<ref name=chadyn>{{citation
 | last = Chan | first = Timothy M. | author-link = Timothy M. Chan
 | doi = 10.1145/1706591.1706596
 | issue = 3
 | journal = [[Journal of the ACM]]
 | mr = 2665885
 | page = Article 16
 | title = A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
 | volume = 57
 | year = 2010| s2cid = 47454142 }}</ref>

<ref name=chalev>{{citation
 | last = Chan | first = Timothy M. | author-link = Timothy M. Chan
 | doi = 10.1007/s00454-002-2840-2
 | issue = 3
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1961005
 | pages = 375–393
 | title = On levels in arrangements of curves
 | volume = 29
 | year = 2003| s2cid = 18966889 | doi-access = free
 }}</ref>

<ref name=chrvp>{{citation
 | last1 = Clementi | first1 = Andrea E. F.
 | last2 = Huiban | first2 = Gurvan
 | last3 = Rossi | first3 = Gianluca
 | last4 = Verhoeven | first4 = Yann C.
 | last5 = Penna | first5 = Paolo
 | contribution = On the approximation ratio of the MST-based heuristic for the energy-efficient broadcast problem in static ad-hoc radio networks
 | doi = 10.1109/IPDPS.2003.1213407
 | page = 222
 | publisher = IEEE Computer Society
 | title = 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 22-26 April 2003, Nice, France, Proceedings
 | year = 2003| s2cid = 17863487
 }}</ref>

<ref name=clarkson>{{citation
 | last = Clarkson | first = Kenneth L. | author-link = Kenneth L. Clarkson
 | doi = 10.1007/BF01553902
 | issue = 1–4
 | journal = [[Algorithmica]]
 | mr = 1019387
 | pages = 461–469
 | title = An algorithm for geometric minimum spanning trees requiring nearly linear expected time
 | volume = 4
 | year = 1989| s2cid = 22176641 }}</ref>

<ref name=comment>{{citation
 | last = Toussaint | first = G. T. | author-link = Godfried Toussaint
 | doi = 10.1049/el:19800611
 | issue = 22
 | journal = Electronics Letters
 | page = 860
 | title = Comment: Algorithms for computing relative neighborhood graph
 | volume = 16
 | year = 1980| bibcode = 1980ElL....16..860T }}; reply by Urquhart, [[doi:10.1049/el:19800612|pp. 860–861]]</ref>

<ref name=devillers>{{citation
 | last = Devillers | first = Olivier
 | doi = 10.1142/S021819599200007X
 | issue = 1
 | journal = International Journal of Computational Geometry & Applications
 | mr = 1159844
 | pages = 97–111
 | title = Randomization yields simple {{math|''O''(''n'' log<sup>*</sup> ''n)''}} algorithms for difficult {{math|&Omega;(''n'')}} problems
 | url = https://hal.inria.fr/inria-00167206/file/hal.pdf
 | volume = 2
 | year = 1992| s2cid = 60203
 }}</ref>

<ref name=dwyer>{{citation
 | last = Dwyer | first = Rex A.
 | doi = 10.1007/BF02574694
 | issue = 4
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1098813
 | pages = 343–367
 | title = Higher-dimensional Voronoi diagrams in linear expected time
 | volume = 6
 | year = 1991| doi-access = free
 }}</ref>

<ref name=eppstein>{{citation
 | last = Eppstein | first = David | author-link = David Eppstein
 | editor1-last = Sack | editor1-first = J.-R. | editor1-link = Jörg-Rüdiger Sack
 | editor2-last = Urrutia | editor2-first = J. | editor2-link = Jorge Urrutia Galicia
 | contribution = Spanning trees and spanners
 | contribution-url = https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf
 | mr = 1746681
 | pages = 425–461
 | publisher = Elsevier
 | title = Handbook of Computational Geometry
 | year = 1999}}</ref>

<ref name=ew94>{{citation
 | last1 = Eades | first1 = Peter | author1-link = Peter Eades
 | last2 = Whitesides | first2 = Sue | author2-link = Sue Whitesides
 | doi = 10.1007/s004539900037
 | issue = 1
 | journal = [[Algorithmica]]
 | mr = 1394494
 | pages = 60–82
 | title = The realization problem for Euclidean minimum spanning trees is NP-hard
 | volume = 16
 | year = 1996}}</ref>

<ref name=extrema>{{citation
 | last = Eppstein | first = David | author-link = David Eppstein
 | doi = 10.1007/BF02574030
 | issue = 1
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1300511
 | pages = 111–122
 | title = Dynamic Euclidean minimum spanning trees and extrema of binary functions
 | volume = 13
 | year = 1995| s2cid = 7339165 | doi-access = free
 }}</ref>

<ref name=fknp>{{citation
 | last1 = Flammini | first1 = Michele
 | last2 = Klasing | first2 = Ralf
 | last3 = Navarra | first3 = Alfredo
 | last4 = Perennes | first4 = Stephane
 | doi = 10.1007/s00453-007-9077-7
 | issue = 4
 | journal = Algorithmica
 | mr = 2358524
 | pages = 318–336
 | title = Improved approximation results for the minimum energy broadcasting problem
 | volume = 49
 | year = 2007| s2cid = 11982404
 }}</ref>

<ref name=frakau>{{citation
 | last1 = Frati | first1 = Fabrizio
 | last2 = Kaufmann | first2 = Michael
 | doi = 10.1016/j.comgeo.2011.05.005
 | issue = 9
 | journal = [[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]
 | mr = 2819643
 | pages = 529–543
 | title = Polynomial area bounds for MST embeddings of trees
 | volume = 44
 | year = 2011| s2cid = 5634139
 | doi-access = free
 }}</ref>

<ref name=gilpol>{{citation
 | last1 = Gilbert | first1 = E. N. | author1-link = Edgar Gilbert
 | last2 = Pollak | first2 = H. O. | author2-link = Henry O. Pollak
 | doi = 10.1137/0116001
 | journal = [[SIAM Journal on Applied Mathematics]]
 | jstor = 2099400
 | mr = 223269
 | pages = 1–29
 | title = Steiner minimal trees
 | volume = 16
 | year = 1968| issue = 1 }}</ref>

<ref name=gowros>{{citation
 | last1 = Gower | first1 = J. C.
 | last2 = Ross | first2 = G. J. S.
 | doi = 10.2307/2346439
 | journal = Applied Statistics
 | jstor = 2346439
 | mr = 242315
 | pages = 54–61
 | title = Minimum spanning trees and single linkage cluster analysis
 | volume = 18
 | year = 1969| issue = 1
 }}</ref>

<ref name=history>{{citation
 | last1 = Graham | first1 = R. L. | author1-link = Ronald Graham
 | last2 = Hell | first2 = Pavol | author2-link = Pavol Hell
 | doi = 10.1109/mahc.1985.10011
 | issue = 1
 | journal = IEEE Annals of the History of Computing
 | mr = 0783327
 | pages = 43–57
 | title = On the history of the minimum spanning tree problem
 | volume = 7
 | year = 1985| s2cid = 10555375 }}</ref>

<ref name=king>{{citation
 | last = King | first = James A.
 | contribution = Realization of degree 10 minimum spanning trees in 3-space
 | contribution-url = https://www.cs.queensu.ca/cccg/papers/cccg11.pdf
 | pages = 39–42
 | title = Proceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006, August 14-16, 2006, Queen's University, Ontario, Canada
 | year = 2006}}</ref>

<ref name=kissing>{{citation|last1=Pfender|first1=Florian|last2=Ziegler|first2=Günter M.|author-link2=Günter M. Ziegler|title=Kissing numbers, sphere packings, and some unexpected proofs|journal=[[Notices of the American Mathematical Society]]|date=September 2004|pages=873–883|url=https://www.ams.org/notices/200408/fea-pfender.pdf}}</ref>

<ref name=kkt>{{citation
 | last1 = Karger | first1 = David R. | author1-link = David Karger
 | last2 = Klein | first2 = Philip N.
 | last3 = Tarjan | first3 = Robert E. | author3-link = Robert Tarjan
 | doi = 10.1145/201019.201022
 | issue = 2
 | journal = [[Journal of the ACM]]
 | mr = 1409738
 | pages = 321–328
 | title = A randomized linear-time algorithm to find minimum spanning trees
 | volume = 42
 | year = 1995| s2cid = 832583 | doi-access = free
 }}</ref>

<ref name=kln>{{citation
 | last1 = Krznaric | first1 = Drago
 | last2 = Levcopoulos | first2 = Christos
 | last3 = Nilsson | first3 = Bengt J.
 | issue = 4
 | journal = Nordic Journal of Computing
 | mr = 1736451
 | pages = 446–461
 | title = Minimum spanning trees in <math>d</math> dimensions
 | volume = 6
 | year = 1999}}. This version of this paper is not available online; instead, see the 1997 conference version of the same paper, {{doi|10.1007/3-540-63397-9_26}}.</ref>

<ref name=kti>{{citation
 | last1 = Katoh | first1 = N.
 | last2 = Tokuyama | first2 = T.
 | last3 = Iwano | first3 = K.
 | doi = 10.1007/BF02574035
 | issue = 2
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1314960
 | pages = 161–176
 | title = On minimum and maximum spanning trees of linearly moving points
 | volume = 13
 | year = 1995| doi-access = free
 }}</ref>

<ref name=lee>{{citation
 | last = Lee | first = In-Kwon
 | doi = 10.1016/S0167-8396(99)00044-8
 | issue = 2
 | journal = Computer Aided Geometric Design
 | mr = 1733203
 | pages = 161–177
 | title = Curve reconstruction from unorganized points
 | volume = 17
 | year = 2000}}</ref>

<ref name=lobwei>{{citation
 | last1 = Loberman | first1 = H.
 | last2 = Weinberger | first2 = A.
 | date = October 1957
 | doi = 10.1145/320893.320896
 | issue = 4
 | journal = [[Journal of the ACM]]
 | pages = 428–437
 | title = Formal procedures for connecting terminals with a minimum total wire length
 | volume = 4| s2cid = 7320964
 }}</ref>

<ref name=mares>{{citation
 | last = Mareš | first = Martin
 | issue = 3
 | journal = Archivum Mathematicum
 | mr = 2107027
 | pages = 315–320
 | title = Two linear time algorithms for MST on minor closed graph classes
 | url = https://www.emis.de/journals/AM/04-3/am1139.pdf
 | volume = 40
 | year = 2004}}</ref>

<ref name=monsur>{{citation
 | last1 = Monma | first1 = Clyde
 | last2 = Suri | first2 = Subhash | author2-link = Subhash Suri
 | doi = 10.1007/BF02293049
 | issue = 3
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1174358
 | pages = 265–293
 | title = Transitions in geometric minimum spanning trees
 | volume = 8
 | year = 1992| s2cid = 30101649
 | doi-access = free
 }}</ref>

<ref name=mrg>{{citation
 | last1 = March | first1 = William B.
 | last2 = Ram | first2 = Parikshit
 | last3 = Gray | first3 = Alexander G.
 | editor1-last = Rao | editor1-first = Bharat
 | editor2-last = Krishnapuram | editor2-first = Balaji
 | editor3-last = Tomkins | editor3-first = Andrew
 | editor4-last = Yang | editor4-first = Qiang
 | contribution = Fast Euclidean minimum spanning tree: algorithm, analysis, and applications
 | doi = 10.1145/1835804.1835882
 | pages = 603–612
 | title = Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010
 | year = 2010| s2cid = 186025
 }}</ref>

<ref name=msvw>{{citation
 | last1 = Meulemans | first1 = Wouter
 | last2 = Speckmann | first2 = Bettina | author2-link = Bettina Speckmann
 | last3 = Verbeek | first3 = Kevin
 | last4 = Wulms | first4 = Jules
 | editor1-last = Bender | editor1-first = Michael A.
 | editor2-last = Farach-Colton | editor2-first = Martin | editor2-link = Martin Farach-Colton
 | editor3-last = Mosteiro | editor3-first = Miguel A.
 | contribution = A framework for algorithm stability and its application to kinetic Euclidean MSTs
 | doi = 10.1007/978-3-319-77404-6_58
 | pages = 805–819
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = LATIN 2018: Theoretical Informatics – 13th Latin American Symposium, Buenos Aires, Argentina, April 16–19, 2018, Proceedings
 | volume = 10807
 | year = 2018| s2cid = 4709616
 | url = https://research.tue.nl/nl/publications/bde45eae-314a-42b4-8dca-9a0a420f38e1
 }}</ref>

<ref name=nzz>{{citation
 | last1 = Narasimhan | first1 = Giri
 | last2 = Zachariasen | first2 = Martin
 | last3 = Zhu | first3 = Jianlin
 | contribution = Experiments with computing geometric minimum spanning trees
 | pages = 183–196
 | title = Proceedings of the 2nd Workshop on Algorithm Engineering and Experiments
 | year = 2000}}</ref>

<ref name=offline>{{citation
 | last = Eppstein | first = David | author-link = David Eppstein
 | doi = 10.1006/jagm.1994.1033
 | issue = 2
 | journal = Journal of Algorithms
 | mr = 1291541
 | pages = 237–250
 | title = Offline algorithms for dynamic minimum spanning tree problems
 | volume = 17
 | year = 1994| url = https://escholarship.org/uc/item/6j46j8nc }}</ref>

<ref name=penrose>{{citation
 | last = Penrose | first = Mathew D.
 | doi = 10.1214/aoap/1034625335
 | issue = 2
 | journal = The Annals of Applied Probability
 | mr = 1442317
 | pages = 340–361
 | title = The longest edge of the random minimal spanning tree
 | volume = 7
 | year = 1997| doi-access = free
 }}</ref>

<ref name=presha>{{citation
 | last1 = Preparata | first1 = Franco P. | author1-link = Franco P. Preparata
 | last2 = Shamos | first2 = Michael Ian | author2-link = Michael Ian Shamos
 | doi = 10.1007/978-1-4612-1098-6
 | isbn = 0-387-96131-3
 | mr = 805539
 | page = 263
 | publisher = Springer-Verlag, New York
 | series = Texts and Monographs in Computer Science
 | title = Computational Geometry: An Introduction
 | year = 1985| s2cid = 206656565 }}</ref>

<ref name=rakwz>{{citation
 | last1 = Rahmati | first1 = Zahed
 | last2 = Abam | first2 = Mohammad Ali
 | last3 = King | first3 = Valerie | author3-link = Valerie King
 | last4 = Whitesides | first4 = Sue | author4-link = Sue Whitesides
 | last5 = Zarei | first5 = Alireza
 | doi = 10.1016/j.comgeo.2014.12.002
 | issue = 4
 | journal = Computational Geometry: Theory & Applications
 | mr = 3296072
 | pages = 342–359
 | title = A simple, faster method for kinetic proximity problems
 | volume = 48
 | year = 2015| s2cid = 18971251
 | doi-access = free
 }}</ref>

<ref name=robsal>{{citation
 | last1 = Robins | first1 = G.
 | last2 = Salowe | first2 = J. S.
 | doi = 10.1007/BF02570700
 | issue = 2
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1331924
 | pages = 151–165
 | title = Low-degree minimum spanning trees
 | volume = 14
 | year = 1995| s2cid = 16040977
 | doi-access = free
 }}</ref>

<ref name=rzcomb>{{citation
 | last1 = Rahmati | first1 = Zahed
 | last2 = Zarei | first2 = Alireza
 | contribution = Combinatorial changes of Euclidean minimum spanning tree of moving points in the plane
 | contribution-url = https://cccg.ca/proceedings/2010/paper14.pdf
 | pages = 43–45
 | title = Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, Winnipeg, Manitoba, Canada, August 9-11, 2010
 | year = 2010}}</ref>

<ref name=rzkin>{{citation
 | last1 = Rahmati | first1 = Zahed
 | last2 = Zarei | first2 = Alireza
 | doi = 10.1016/j.jda.2012.04.009
 | journal = Journal of Discrete Algorithms
 | mr = 2960341
 | pages = 2–11
 | title = Kinetic Euclidean minimum spanning tree in the plane
 | volume = 16
 | year = 2012| doi-access = free
 }}</ref>

<ref name=shahoe>{{citation
 | last1 = Shamos | first1 = Michael Ian | author1-link = Michael Ian Shamos
 | last2 = Hoey | first2 = Dan
 | contribution = Closest-point problems
 | doi = 10.1109/SFCS.1975.8
 | mr = 0426498
 | pages = 151–162
 | publisher = IEEE Computer Society
 | title = 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975
 | title-link = Symposium on Foundations of Computer Science
 | year = 1975| s2cid = 40615455 }}</ref>

<ref name=ss89>{{citation
 | last1 = Steele | first1 = J. Michael | author1-link = J. Michael Steele
 | last2 = Snyder | first2 = Timothy Law | author2-link = Timothy Law Snyder
 | doi = 10.1137/0218019
 | issue = 2
 | journal = [[SIAM Journal on Computing]]
 | mr = 986667
 | pages = 278–287
 | title = Worst-case growth rates of some classical problems of combinatorial optimization
 | volume = 18
 | year = 1989| url = https://repository.upenn.edu/cgi/viewcontent.cgi?article=1048&context=oid_papers }}</ref>

<ref name=sse>{{citation
 | last1 = Steele | first1 = J. Michael | author1-link = J. Michael Steele
 | last2 = Shepp | first2 = Lawrence A.
 | last3 = Eddy | first3 = William F.
 | doi = 10.2307/3214207
 | issue = 4
 | journal = Journal of Applied Probability
 | mr = 913823
 | pages = 809–826
 | title = On the number of leaves of a Euclidean minimal spanning tree
 | volume = 24
 | year = 1987| jstor = 3214207 | s2cid = 29026025 }}</ref>

<ref name=steele>{{citation
 | last = Steele | first = J. Michael | author-link = J. Michael Steele
 | doi = 10.1214/aop/1176991596 | doi-access = free
 | issue = 4
 | journal = [[Annals of Probability]]
 | jstor = 2243991
 | mr = 0958215
 | pages = 1767–1787
 | title = Growth rates of Euclidean minimal spanning trees with power weighted edges
 | volume = 16
 | year = 1988}}</ref>

<ref name=topp>{{citation|url=https://topp.openproblem.net/p5|publisher=Smith College|work=The Open Problems Project|title=Problem 5: Euclidean Minimum Spanning Tree|date=2001–2002|first1=J.|last1=O'Rourke|author1-link=Joseph O'Rourke (professor)|first2=E.|last2=Demaine|author2-link=Erik Demaine}}</ref>

<ref name=urban>{{citation
 | last1 = Wu | first1 = Bin
 | last2 = Yu | first2 = Bailang
 | last3 = Wu | first3 = Qiusheng
 | last4 = Chen | first4 = Zuoqi
 | last5 = Yao | first5 = Shenjun
 | last6 = Huang | first6 = Yan
 | last7 = Wu | first7 = Jianping
 | date = October 2017
 | doi = 10.1080/13658816.2017.1384830
 | issue = 3
 | journal = International Journal of Geographical Information Science
 | pages = 450–475
 | title = An extended minimum spanning tree method for characterizing local urban patterns
 | volume = 32| s2cid = 46772272
 }}</ref>

<ref name=wclf>{{citation
 | last1 = Wan | first1 = P.-J.
 | last2 = Călinescu | first2 = G.
 | last3 = Li | first3 = X.-Y.
 | last4 = Frieder | first4 = O.
 | doi = 10.1023/a:1020381720601
 | issue = 6
 | journal = Wireless Networks
 | pages = 607–617
 | title = Minimum-energy broadcasting in static ad hoc wireless networks
 | volume = 8
 | year = 2002| s2cid = 1297518
 }}</ref>

<ref name=yao82>{{citation
 | last = Yao | first = Andrew Chi Chih | author-link = Andrew Yao
 | doi = 10.1137/0211059
 | issue = 4
 | journal = [[SIAM Journal on Computing]]
 | mr = 677663
 | pages = 721–736
 | title = On constructing minimum spanning trees in {{mvar|k}}-dimensional spaces and related problems
 | volume = 11
 | year = 1982}}</ref>

<ref name=yao89>{{citation
 | last = Yao | first = Andrew Chi-Chih | author-link = Andrew Yao
 | doi = 10.1137/0220041
 | issue = 4
 | journal = [[SIAM Journal on Computing]]
 | mr = 1105929
 | pages = 655–668
 | title = Lower bounds for algebraic computation trees with integer inputs
 | volume = 20
 | year = 1991}}</ref>

<ref name=zahn>{{citation
 | last = Zahn | first = C. T.
 | contribution = Using the minimum spanning tree to recognize dotted and dashed curves
 | contribution-url = https://cds.cern.ch/record/1050916
 | title = 1st International Computing Symposium, Davos, Switzerland, 4–7 September 1973
 | year = 1973}}</ref>

}}


==बाहरी संबंध==
* [https://mlpack.org/doc/stable/doxygen/emst_tutorial.html EMST tutorial], [[mlpack]] documentation

{{DEFAULTSORT:Euclidean Minimum Spanning Tree}}

[[Category:CS1 errors|Euclidean Minimum Spanning Tree]]
[[Category:Created On 25/06/2023|Euclidean Minimum Spanning Tree]]
[[Category:Lua-based templates|Euclidean Minimum Spanning Tree]]
[[Category:Machine Translated Page|Euclidean Minimum Spanning Tree]]
[[Category:Pages with script errors|Euclidean Minimum Spanning Tree]]
[[Category:Short description with empty Wikidata description|Euclidean Minimum Spanning Tree]]
[[Category:Template documentation pages|Short description/doc]]
[[Category:Templates Vigyan Ready|Euclidean Minimum Spanning Tree]]
[[Category:Templates that add a tracking category|Euclidean Minimum Spanning Tree]]
[[Category:Templates that generate short descriptions|Euclidean Minimum Spanning Tree]]
[[Category:Templates using TemplateData|Euclidean Minimum Spanning Tree]]