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

विमान में 25 यादृच्छिक बिंदुओं का यूक्लिडियन न्यूनतम प्रसारित हुआ ट्री

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

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

परिभाषा और संबंधित समस्याएँ

एक यूक्लिडियन न्यूनतम प्रसारित हुए ट्री, के एक समुच्चय के लिए $n$ यूक्लिडियन विमान या यूक्लिडियन स्पेस में बिंदु, रेखा खंडों की एक प्रणाली होती होती है, जिसमें मात्र दिए गए बिंदु उनके अंतिम बिंदु होते हैं, जिनके संघ में एक जुड़े हुए समुच्चय के सभी बिंदु सम्मलित होते हैं, और जिसमें ऐसी किसी भी प्रणाली की न्यूनतम संभव कुल लंबाई होती है। ऐसे नेटवर्क में खंडों का बहुभुज वलय नहीं हो सकता; यदि कोई अस्तित्व में है, तो बहुभुज के एक किनारे को हटाकर नेटवर्क को छोटा किया जा सकता है। इसलिए, न्यूनतम लंबाई वाला नेटवर्क एक ट्री (ग्राफ़ सिद्धांत) बनाता है। यह अवलोकन समतुल्य परिभाषा की ओर ले जाता है कि यूक्लिडियन न्यूनतम प्रसारित हुए ट्री, न्यूनतम कुल लंबाई के दिए गए बिंदुओं के जोड़े के मध्य रेखा खंडों का एक ट्री होता है।^[1] इस प्रकार उसी ट्री को भारित पूर्ण ग्राफ के न्यूनतम प्रसारित हुए ट्री के रूप में भी वर्णित किया जा सकता है, जिसमें दिए गए बिंदु इसके शीर्ष के रूप में होते हैं और बिंदुओं के मध्य की दूरी किनारे के वजन के रूप में होती है।^[2] समान बिंदुओं पर एक से अधिक न्यूनतम प्रसारित हुए ट्री हो सकते हैं। उदाहरण के लिए, एक नियमित बहुभुज के शीर्षों के लिए, बहुभुज के किसी भी किनारे को हटाने से न्यूनतम प्रसारित हुए ट्री का निर्माण होता है।^[3]

यूक्लिडियन मिनिमम स्पैनिंग ट्री पर प्रकाशन सामान्यतः इसे ईएमएसटी के रूप में संक्षिप्त करते हैं।^[4]^[5] इन्हें ज्यामितीय न्यूनतम प्रसारित हुए ट्री भी कहा जा सकता है,^[6]^[7] लेकिन उस शब्द का उपयोग सामान्यतः गैर-यूक्लिडियन दूरियों वाले ज्यामितीय स्थानों के लिए किया जा सकता है, जैसे कि $L p$ स्पेस।^[8] जब यूक्लिडियन बिंदु समुच्चयों का संदर्भ स्पष्ट हो, तो उन्हें मात्र न्यूनतम प्रसारित हुए ट्री कहा जा सकता है।^[9]^[10]^[11]

इस प्रकार कई अन्य मानक ज्यामितीय नेटवर्क यूक्लिडियन न्यूनतम प्रसारित हुए ट्री से निकटता से संबंधित हैं:

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

गुण

कोण और शीर्ष डिग्री

बारह इकाई गोले एक केंद्रीय इकाई क्षेत्र के सभी स्पर्शरेखा हैं। उनके 13 केंद्र बिंदुओं में से न्यूनतम प्रसारित हुए ट्री का केंद्रीय बिंदु पर डिग्री 12 है।

जब भी यूक्लिडियन न्यूनतम प्रसारित हुए ट्री के दो किनारे एक शीर्ष पर मिलते हैं, तो उन्हें 60° या अधिक का कोण बनाना चाहिए, समानता के साथ मात्र तभी जब वे एक समबाहु त्रिभुज की दो भुजाएँ बनाते हैं। ऐसा इसलिए है, क्योंकि किसी भी तीव्र कोण बनाने वाले दो किनारों के लिए, दो किनारों में से एक को उनके द्वारा बनाए गए त्रिभुज के तीसरे, छोटे किनारे से बदला जा सकता है, जिससे छोटी कुल लंबाई वाला एक ट्री बनता है।^[14] इसकी तुलना में, स्टीनर ट्री की समस्या में एक मजबूत कोण सीमा होती है: इस प्रकार एक सर्वश्रेष्ठ स्टीनर ट्री के सभी कोण कम से कम 120° होते हैं।^[12]

वही 60° कोण सीमा चुंबन संख्या समस्या में भी होती है, यूक्लिडियन अंतरिक्ष में इकाई क्षेत्रों की अधिकतम संख्या को अन्वेषण के लिए जो किसी भी दो क्षेत्रों को प्रतिच्छेद किए बिना (स्पर्शरेखा के एक बिंदु से परे) एक केंद्रीय इकाई क्षेत्र के स्पर्शरेखा हो सकती है। इन क्षेत्रों के केंद्र बिंदुओं में एक तारे (ग्राफ सिद्धांत) के रूप में एक न्यूनतम प्रसारित हुआ ट्री होता है, जिसका केंद्रीय बिंदु अन्य सभी बिंदुओं के निकट होता है। इसके विपरीत, किसी भी शीर्ष $v$ के लिए किसी भी न्यूनतम प्रसारित हुए ट्री के केंद्र में गैर-अतिव्यापी इकाई गोले का निर्माण किया जा सकता है $v$ और इसके प्रत्येक किनारे के साथ बिंदुओं पर दो इकाइयां, $v$ के प्रत्येक निकटतमी के लिए स्पर्शरेखा के साथ इसलिए, $n$ -आयामी स्थान एक शीर्ष की अधिकतम संभव डिग्री (इससे जुड़े प्रसारित हुए ट्री के किनारों की संख्या) में $n$ आयाम में गोले की चुंबन संख्या के बराबर होती है ^[15] इस प्रकार प्लेनर न्यूनतम प्रसारित हुए ट्र की डिग्री अधिकतम छह होती है, और जब एक ट्री की डिग्री छह होती है तो सदैव अधिकतम डिग्री पांच वाला एक और न्यूनतम प्रसारित हुआ ट्री होता है।^[7] त्रि-आयामी न्यूनतम प्रसारित हुए ट्री की डिग्री अधिकतम बारह होती है।^[15] इस प्रकार एकमात्र उच्च आयाम जिसमें चुंबन संख्या का स्पष्ट मान ज्ञात होता है, और इस प्रकार इसमें 4, 8 और 24 आयाम होते हैं।^[16]

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

रिक्त क्षेत्र

यूक्लिडियन न्यूनतम प्रसारित हुए ट्री के लिए खाली क्षेत्र: दिखाए गए लाल किनारे के लिए, इन क्षेत्रों में ट्री का कोई अन्य शीर्ष सम्मलित नहीं हो सकता है। सफेद: सापेक्ष निकटतम ग्राफ को परिभाषित करने वाला खाली लेंस। हल्का नीला: व्यास वृत्त गेब्रियल ग्राफ को परिभाषित करता है और डेलाउने त्रिकोण के लिए एक खाली वृत्त बनाता है। गहरा नीला: एक 60°-120° समचतुर्भुज जो अन्य प्रसारित हुए ट्री के किनारों के समचतुर्भुज के साथ ओवरलैप नहीं हो सकता।

किसी भी किनारे के लिए किसी भी यूक्लिडियन न्यूनतम प्रसारित हुए ट्री का $uv$ , यूवी के साथ दो वृत्तों को उनके त्रिज्या के रूप में प्रतिच्छेद करने से बना लेंस (या वेसिका पिस्किस) इसके आंतरिक भाग में कोई अन्य दिया गया शीर्ष $w$ नहीं हो सकता है। इस प्रकार यदि किसी ट्री का किनारा $uv$ है तो दूसरे प्रकार से रखें जिसके लेंस में तीसरा बिंदु $w$ होता है, तो यह न्यूनतम लंबाई का नहीं होता है। क्योंकि, दो वृत्तों की ज्यामिति के अनुसार, $w$ दोनों के निकट होगा $u$ और $v$ जितना वे एक दूसरे के प्रति निकट होते हैं। इस प्रकार अगर किनारा $uv$ ट्री से हटा दिए जाए, तो $w$ $u$ और $v$ , से किसी एक से जुड़ा रहेगा लेकिन दूसरा नहीं। हटाए गए किनारे को बदलना $uv$ द्वारा $uw$ या $vw$ द्वारा बदला जाता है( इन दोनों किनारों में से जो भी $w$ को शीर्ष पुनः जोड़ता है जहां से इसे अलग किया गया था)। इस प्रकार एक छोटा ट्री उत्पन्न होता है।^[12]

किसी भी किनारे के लिए किसी भी यूक्लिडियन न्यूनतम प्रसारित हुए ट्री का $uv$ 60° और 120° के कोण वाला समचतुर्भुज, जिसमें $uv$ अपने लंबे विकर्ण के रूप में, यह अन्य सभी किनारों द्वारा समान रूप से निर्मित रम्बी से असंयुक्त होता है। इस प्रकार एक समापन बिंदु को साझा करने वाले दो किनारों में ओवरलैपिंग रॉम्बी नहीं हो सकती है, क्योंकि इसका मतलब 60° सेअधिक किनारे का कोण होगा, और दो असंयुक्त किनारों में ओवरलैपिंग रॉम्बी नहीं हो सकती है; यदि वे ऐसा करते, तो दोनों किनारों में से लंबे किनारे को उन्हीं चार शीर्षों के मध्य एक छोटे किनारे से बदला जा सकता है।^[12]

सुपरग्राफ

कुछ ज्यामितीय ग्राफ़ों में बिंदु समुच्चयों में खाली क्षेत्रों को सम्मलित करने वाली परिभाषाएँ होती हैं, जिससे यह पता चलता है कि उनमें हर किनारा सम्मलित है जो यूक्लिडियन न्यूनतम प्रसारित हुए ट्री का एक भाग हो सकता है। इसमे सम्मलित होते है:

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

चूँकि इन ग्राफ़ों के लिए खाली-क्षेत्र मानदंड उत्तरोत्तर कमज़ोर होते जा रहे हैं, ये ग्राफ़ सबग्राफ़ों का एक क्रमबद्ध अनुक्रम बनाते हैं। अर्थात्, उनके किनारों के मध्य उपसमुच्चय संबंध को दर्शाने के लिए ⊆ का उपयोग करते है, इन ग्राफ़ों में निम्नलिखित संबंध होता हैं:

यूक्लिडियन न्यूनतम फैले हुए पेड़ ⊆ सापेक्ष पड़ोस ग्राफ ⊆ उर्कहार्ट ग्राफ ⊆ गेब्रियल ग्राफ ⊆ डेलाउने त्रिभुज होते है।^[18]^[19]

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

कुल लंबाई

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

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

{\sqrt {\frac {\log n}{\pi n}}},

इस प्रकार यह क गैर-स्थिर कारक द्वारा औसत से अधिक लंबा होता है। उच्च संभावना के साथ, सबसे लंबा किनारा प्रसारित हुए ट्री का एक पत्ता बनाता है, और अन्य सभी बिंदुओं से दूर एक बिंदु को उसके निकटतम निकटतमी से जोड़ता है। इस प्रकार बड़ी संख्या में अंकों के लिए, इसके अपेक्षित मूल्य के आसपास सबसे लंबी किनारे की लंबाई का वितरण लाप्लास वितरण में परिवर्तित हो जाता है।^[24]कोई भी ज्यामितीय स्पैनर, एक पूर्ण ज्यामितीय ग्राफ का एक उपग्राफ जिसकी सबसे छोटी पथ समस्या यूक्लिडियन दूरी का अनुमान लगाती है, उसकी कुल किनारे की लंबाई कम से कम न्यूनतम प्रसारित हुए ट्री जितनी बड़ी होनी चाहिए, और एक ज्यामितीय स्पैनर के लिए मानक गुणवत्ता उपायों में से एक इसकी कुल लंबाई और समान बिंदुओं के लिए न्यूनतम प्रसारित हुए ट्री के मध्य का अनुपात इसकी होता है। इस प्रकार स्पैनर के निर्माण की कई विधियाँ होती है ,जैसे कि ग्रीडी ज्यामितीय स्पैनर, इस अनुपात के लिए एक स्थिर सीमा प्राप्त करती हैं।^[13] यह अनुमान लगाया गया है कि स्टीनर अनुपात, विमान में बिंदुओं के समान समुच्चय के लिए न्यूनतम प्रसारित हुए ट्री और स्टीनर ट्री की कुल लंबाई के मध्य सबसे बड़ा संभव अनुपात होता है।

2/{\sqrt {3}}\approx 1.1547

, एक समबाहु त्रिभुज में तीन बिंदुओं का अनुपात होता है।^[12]

उपखंड

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

कम्प्यूटेशनल जटिलता

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

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

दो आयाम

समतल बिंदुओं के न्यूनतम प्रसारित हुए ट्री के अन्वेषण के लिए एक उच्च दृष्टिकोण इस गुण का उपयोग करता है कि यह डेलाउने त्रिकोण का एक उपसमूह होता है:

डेलाउने त्रिभुज की गणना करें, जिसे किया $O(n\log n)$ समय में जा सकता है। क्योंकि डेलाउने त्रिभुज एक समतलीय ग्राफ होता है, इसमें अधिकतम $3n-6$ किनारे होते है।
प्रत्येक किनारे को उसकी (वर्गीकृत) लंबाई के साथ लेबल करें।
एक ग्राफ़ न्यूनतम स्पैनिंग ट्री कलन विधि चलाएँ। क्योंकि वहां $O(n)$ किनरे होते है, किसी भी मानक न्यूनतम स्पैनिंग ट्री कलन विधि का उपयोग द्वारा समय $O(n\log n)$ की इसको आवश्यकता होती है।

परिणाम एक कलन विधि $O(n\log n)$ समय लेता है,^[2] गणना के कुछ प्रारू में सर्वश्रेष्ठ निम्नलिखित दिए गये है (निचली सीमा देखें)।

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

उच्च आयाम

समस्या का सामान्यीकरण $n$ में अंक $d$ -आयामी स्थान $\mathbb {R} ^{d}$ में भी किया जा सकता है। उच्च आयामों में, कनेक्टिविटी डेलाउने त्रिकोण द्वारा निर्धारित की जाती है (जो, इसी तरह, उत्तल पतवार को $d$ -डायमेंशनल संकेतन में विभाजित करती है) इसमें कुछ न्यूनतम प्रसारित हुए ट्री सम्मलित होते हैं; यघपि, त्रिभुज में पूरा ग्राफ़ सम्मलित हो सकता है।^[4] इसलिए, यूक्लिडियन न्यूनतम प्रसारित हुए ट्री को पूर्ण ग्राफ़ के प्रसारित हुए ट्री के रूप में या डेलाउने त्रिकोण के प्रसारित हुए ट्री के रूप में अन्वेषण के लिए दोनों $O(dn^{2})$ समय लेते है। इस प्रकार तीन आयामों के लिए न्यूनतम प्रसारित हुए ट्री को समय $O{\bigl (}(n\log n)^{4/3}{\bigr )}$ में पाया जा सकता है, और किसी भी बड़े आयाम को, प्रदर्शित किये गये समय में पाया जा सकता है:

O\left(n^{2-{\frac {2}{\lceil d/2\rceil +1}}+\varepsilon }\right)

किसी के लिए

\varepsilon >0

- संपूर्ण ग्राफ़ औलेकिनउने त्रिभुज कलन विधि के लिए द्विघात समय सीमा से अधिक शीघ्र होता है।^[4]

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

किसी भी सीमित आयाम में समान रूप से यादृच्छिक बिंदु समुच्चय के लिए, याओ ग्राफ^[20] या डेलाउने त्रिकोण में किनारों की रैखिक अपेक्षित संख्या होती है, इसमें न्यूनतम प्रसारित हुए ट्री होने की गारंटी होती है, और रैखिक अपेक्षित समय में इसका निर्माण किया जा सकता है।^[21]^[6]^[30] इन ग्राफ़ों से, अपेक्षित रैखिक समय एमएसटी कलन विधि का उपयोग करके, न्यूनतम स्पैनिंग ट्री का निर्माण रैखिक समय में किया जा सकता है।^[31] चूकिं, क्लस्टर्ड डेटा से आने वाले इनपुट पर इन तरीकों केव्यर्थ प्रदर्शन ने कलन विधि इंजीनियरिंग शोधकर्ताओं को कुछ हद तक धीमी गति से प्रकार विकसित करने के लिए प्रेरित किया है यादृच्छिक इनपुट या इनपुट के लिए $O(n\log n)$ समयबद्ध, जिनकी दूरी और क्लस्टरिंग यादृच्छिक डेटा के समान होती है, जबकि वास्तविक दुनिया डेटा पर उच्चतम प्रदर्शन प्रदर्शित करती है।^[8]^[32]^[5]

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

गतिशील और गतिज(काइनेटिक)

यूक्लिडियन न्यूनतम प्रसारित हुए ट्री को चलती या बदलते बिंदुओं की प्रणालियों के लिए कई अलग-अलग ढंग से सामान्यीकृत किया गया है:

यदि बिंदुओं का एक समुच्चय गतिशील सम्मिलन या बिंदुओं के विलोपन के अनुक्रम से होकर निकलता है, तो इनमें से प्रत्येक अद्यतन बिंदुओं के न्यूनतम प्रसारित हुए ट्री में परिवर्तन की एक सीमित मात्रा को प्रेरित करता है। इस प्रकार जब अद्यतन अनुक्रम पहले से ज्ञात होता है, तो विमान में बिंदुओं के लिए, प्रत्येक प्रविष्टि या विलोपन के बाद परिवर्तन समय $O(\log ^{2}n)$ पर पाया जा सकता है। ^[34] जब अद्यतनों को ऑनलाइन कलन विधि प्रकार से पलेकिनत किया जाता है, तो धीमी (परन्तु फिर भी बहु-लघुगणकीय) $O(\log ^{10}n)$ समयबद्धता ज्ञात होती है।^[35] इस प्रकार समस्या के उच्च-आयामी संस्करणों के लिए प्रति अद्यतन समय धीमा होता है, परन्तु फिर भी अधरेखीय होता है।^[36]
$n$ स्थिर गति के लिए एक साथ, या अधिक सामान्य बीजगणितीय गति के साथ रैखिक रूप से आगे बढ़ने वाले बिंदु, न्यूनतम प्रसारित हुए ट्री स्वैप के अनुक्रम से बदल जाएंगे, जिसमें एक किनारा हटा दिया जाता है और दूसरा इसे उस समय में बदल देता है जहां दोनों की लंबाई समान होती है।^[37] इस प्रकार रैखिक गतियों के लिए, परिवर्तनों की संख्या अधिक से अधिक $n^{25/9}$ से थोड़ी अधिक होती है।^[38] अधिक सामान्य बीजगणितीय गतियों के लिए, डेवनपोर्ट-शिन्ज़ेल अनुक्रमों के सिद्धांत के आधार पर, स्वैप की संख्या पर एक निकट-घन ऊपरी सीमा होती है।^[39]
न्यूनतम गतिमान स्पैनिंग ट्री समस्या फिर से समय के अंतराल पर निरंतर गति के साथ रैखिक रूप से आगे बढ़ने वाले बिन्दुओं से संबंधित होती है, और एक ऐसे ट्री की खोज करती है जो इस अंतराल के समय किसी भी क्षण होने वाले वजन के अधिकतम योग को कम कर दे। त्रुटिहीन गणना करना एनपी-कठिन होता है, परन्तु बहुपद समय में दो के कारक के भीतर इसका अनुमान लगाया जा सकता है।^[40]
गतिज यूक्लिडियन न्यूनतम प्रसारित हुए ट्री समस्या एक गतिज डेटा संरचना की मांग करती है जो न्यूनतम स्पैनिंग ट्री को बनाए रख सके क्योंकि इसके बिंदु निरंतर गति और सम्मिलन और विलोपन दोनों से गुजरते हैं। इस प्रकार कई पत्रों ने ऐसी संरचनाओं का अध्ययन किया है,^[41]^[42]^[43]^[44]^[45] और जो लगभग घन-कुल समय के साथ बीजगणितीय रूप से गतिशील बिंदुओं के लिए एक गतिज संरचना ज्ञात होती है, जो स्वैप की संख्या की सीमा से लगभग समान होती है।^[44]

निचली सीमा

स्पर्शोन्मुख निचली सीमा $\Omega (n\log n)$ यूक्लिडियन न्यूनतम प्रसारित हुए ट्री की समस्या को गणना के प्रतिबंधित प्रारूप में स्थापित किया जा सकता है। इनमें बीजगणितीय निर्णय ट्री और बीजगणितीय संगणना ट्री प्रारूप सम्मलित होता हैं, जिसमें कलन विधि को मात्र कुछ प्रतिबंधित प्राइमेटिव्स के माध्यम से इनपुट बिंदुओं तक पहुंच होती है जो उनके निर्देशांक पर सरल बीजगणितीय गणना करते हैं। इस प्रकार इन प्रारूप में, अंक समस्या की निकटतम जोड़ी की आवश्यकता होती है, परन्तु निकटतम जोड़ी आवश्यक रूप से न्यूनतम प्रसारित हुए ट्री का एक किनारा होता है, इसलिए न्यूनतम प्रसारित हुए ट्री कोभी इतने समय $\Omega (n\log n)$ की आवश्यकता होती है। इसलिए, समय में समतल न्यूनतम प्रसारित हुए ट्री के निर्माण के लिए कलन विधि $O(n\log n)$ इस प्रारूप के भीतर, उदाहरण के लिए डेलाउने त्रिभुज का उपयोग करके, सर्वश्रेष्ठ होते हैं।^[46] यघपि, ये निचली सीमाएँ पूर्णांक बिंदु निर्देशांक के साथ गणना के प्रारूप पर लागू नहीं होती हैं, जिसमें उन निर्देशांक पर बिटवाइज़ संचालन और रैंडम एक्सेस संचालन की अनुमति प्राप्त होती है। इस प्रकार इन प्रारूपो में, तेज़ कलन विधि संभव होता हैं, जैसा कि ऊपर बताया गया है।^[26]

अनुप्रयोग

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

न्यूनतम प्रसारित हुए ट्री एकल-लिंकेज क्लस्टरिंग से निकटता से संबंधित होते हैं, जो पदानुक्रमित क्लस्टरिंग के कई विधियों में से एक होता है। इस प्रकार न्यूनतम प्रसारित हुए ट्री के किनारे, उनकी लंबाई के अनुसार क्रमबद्ध, इस क्लस्टरिंग विधि में समूहों को बड़े समूहों में विलय करने का क्रम देते हैं। एक बार जब ये किनारे मिल जाते हैं, तो किसी भी कलन विधि द्वारा, उनका उपयोग $O(n\log n)$ समय में सिंगल-लिंकेज क्लस्टरिंग के निर्माण के लिए किया जा सकता है।^[1] चूकिं सिंगल-लिंकेज क्लस्टरिंग द्वारा निर्मित लंबे पतले क्लस्टर आकार कुछ प्रकार के डेटा, जैसे कि मिश्रण प्रारूप , के लिए व्यर्थ हो सकते हैं, यह उन अनुप्रयोगों में एक अच्छा विकल्प हो सकता है जहां क्लस्टर से स्वयं लंबे पतले आकार की उम्मीद की जाती है, जैसे कि आकाशगंगाओं के काले पदार्थ के प्रभामंडल का प्रारूप करना होता है।^[5] इस प्रकार भौगोलिक सूचना विज्ञान में, कई शोधकर्ता समूहों ने भवन के सार्थक समूहों की पहचान करने के लिए भवनों के केंद्रक के न्यूनतम प्रसारित हुए ट्री का उपयोग किया है, उदाहरण के लिए किसी अन्य प्रकार से असंगत के रूप में पहचाने गए किनारों को हटाकर किया था।^[49]

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

न्यूनतम प्रसारित हुए ट्री का एक अन्य अनुप्रयोग यूक्लिडियन ट्रैवलिंग सेल्समैन समस्या के लिए एक निरंतर-कारक सन्निकटन कलन विधि होती है, जो एक बिंदु समुच्चय के सबसे छोटे बहुभुजीकरण अन्वेषण की समस्या होती है। इस प्रकार न्यूनतम प्रसारित हुए ट्री की सीमा के चारों ओर घूमना सर्वश्रेष्ठ लंबाई के दो के कारक के भीतर सर्वश्रेष्ठ ट्रैवलिंग सेल्समैन टूर का अनुमान लगा सकता है।^[2] चूकिं, अधिक स्पष्ट बहुपद समय सन्निकटन योजना इस समस्या के लिए जानी जाती हैं।^[52] वायरलेस तदर्थ नेटवर्क में, न्यूनतम प्रसारित हुए ट्री में पथों के साथ प्रसारण (नेटवर्किंग) संदेश न्यूनतम-ऊर्जा प्रसारण रूटिंग का स्पष्ट अनुमान हो सकता है, जिसकी पुनः त्रुटिहीन गणना करना कठिन होता है।^[53]^[54]^[55]^[56]

प्रतीति

यूक्लिडियन न्यूनतम प्रसारित हुए ट्री के लिए प्राप्ति की समस्या इनपुट के रूप में एक अमूर्त ट्री (ग्राफ सिद्धांत) लेती है और ट्री के प्रत्येक शीर्ष (कुछ निश्चित आयाम के स्थान में) के लिए एक ज्यामितीय स्थान की जाँच करती है, जैसे कि दिया गया ट्री न्यूनतम प्रसारित हुए ट्री के बराबर होता है। प्रत्येक अमूर्त ट्री को ऐसी अनुभूति नहीं होती; उदाहरण के लिए, ट्री को प्रत्येक शीर्ष की डिग्री पर बंधी चुंबन संख्या का पालन करना होता है। इस प्रकार अतिरिक्त प्रतिबंध उपस्थित होता हैं; उदाहरण के लिए, एक समतल न्यूनतम प्रसारित हुए ट्री के लिए यह संभव नहीं है कि उसका डिग्री-छह का शीर्ष पांच या छह डिग्री के शीर्ष के निकट हो।^[7] यह निर्धारित करना कि क्या द्वि-आयामी अनुभूति उपस्थित है, एनपी-कठोर होता है। यघपि, कठोरता का प्रमाण इस तथ्य पर निर्भर करता है कि एक ट्री में डिग्री-छह शीर्षों में प्रतीति का एक बहुत ही सीमित समुच्चय होता है: ऐसे शीर्ष के निकटतमियों को उस शीर्ष पर केंद्रित एक नियमित षट्भुज के शीर्ष पर रखा जाना चाहिए।^[57] इस प्रकार अधिकतम डिग्री पांच के ट्री के लिए, एक समतलीय प्रतीति सदैव उपस्थित रहता है।^[7] इसी तरह, अधिकतम डिग्री दस के ट्री के लिए, एक त्रि-आयामी अनुभूति सदैव उपस्थित रहती है।^[10] इन प्रतीति के लिए, कुछ ट्री को उनके सबसे छोटे किनारे की लंबाई के सापेक्ष घातीय लंबाई के किनारों और घातीय क्षेत्र के बाउंडिंग बॉक्स की आवश्यकता हो सकती है।^[58] अधिकतम डिग्री चार के ट्री में छोटे समतलीय प्रतीति होते हैं, जिनमें बहुपद रूप से बंधे किनारे की लंबाई और सीमांकित डिब्बे होते हैं।^[9]

यह भी देखें

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

संदर्भ

↑ ^{Jump up to: 1.0} ^1.1 Gower, J. C.; Ross, G. J. S. (1969), "Minimum spanning trees and single linkage cluster analysis", Applied Statistics, 18 (1): 54–61, doi:10.2307/2346439, JSTOR 2346439, MR 0242315
↑ ^{Jump up to: 2.0} ^2.1 ^2.2 ^2.3 Shamos, Michael Ian; Hoey, Dan (1975), "Closest-point problems", 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, IEEE Computer Society, pp. 151–162, doi:10.1109/SFCS.1975.8, MR 0426498, S2CID 40615455
↑ Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David (2006), "On the spanning ratio of Gabriel graphs and β-skeletons", SIAM Journal on Discrete Mathematics, 20 (2): 412–427, doi:10.1137/S0895480197318088, MR 2257270
↑ ^{Jump up to: 4.0} ^4.1 ^4.2 ^4.3 Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O.; Welzl, E. (1991), "Euclidean minimum spanning trees and bichromatic closest pairs", Discrete & Computational Geometry, Springer, 6 (1): 407–422, doi:10.1007/BF02574698, MR 1115099
↑ ^{Jump up to: 5.0} ^5.1 ^5.2 March, William B.; Ram, Parikshit; Gray, Alexander G. (2010), "Fast Euclidean minimum spanning tree: algorithm, analysis, and applications", in Rao, Bharat; Krishnapuram, Balaji; Tomkins, Andrew; Yang, Qiang (eds.), Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010, pp. 603–612, doi:10.1145/1835804.1835882, S2CID 186025
↑ ^{Jump up to: 6.0} ^6.1 Clarkson, Kenneth L. (1989), "An algorithm for geometric minimum spanning trees requiring nearly linear expected time", Algorithmica, 4 (1–4): 461–469, doi:10.1007/BF01553902, MR 1019387, S2CID 22176641
↑ ^{Jump up to: 7.0} ^7.1 ^7.2 ^7.3 Monma, Clyde; Suri, Subhash (1992), "Transitions in geometric minimum spanning trees", Discrete & Computational Geometry, 8 (3): 265–293, doi:10.1007/BF02293049, MR 1174358, S2CID 30101649
↑ ^{Jump up to: 8.0} ^8.1 Narasimhan, Giri; Zachariasen, Martin; Zhu, Jianlin (2000), "Experiments with computing geometric minimum spanning trees", Proceedings of the 2nd Workshop on Algorithm Engineering and Experiments, pp. 183–196
↑ ^{Jump up to: 9.0} ^9.1 Frati, Fabrizio; Kaufmann, Michael (2011), "Polynomial area bounds for MST embeddings of trees", Computational Geometry: Theory and Applications, 44 (9): 529–543, doi:10.1016/j.comgeo.2011.05.005, MR 2819643, S2CID 5634139
↑ ^{Jump up to: 10.0} ^10.1 King, James A. (2006), "Realization of degree 10 minimum spanning trees in 3-space" (PDF), Proceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006, August 14-16, 2006, Queen's University, Ontario, Canada, pp. 39–42
↑ ^{Jump up to: 11.0} ^11.1 Krznaric, Drago; Levcopoulos, Christos; Nilsson, Bengt J. (1999), "Minimum spanning trees in $d$ dimensions", Nordic Journal of Computing, 6 (4): 446–461, MR 1736451. 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.
↑ ^{Jump up to: 12.0} ^12.1 ^12.2 ^12.3 ^12.4 ^12.5 ^12.6 Gilbert, E. N.; Pollak, H. O. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400, MR 0223269
↑ ^{Jump up to: 13.0} ^13.1 ^13.2 ^13.3 Eppstein, David (1999), "Spanning trees and spanners" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425–461, MR 1746681
↑ Georgakopoulos, George; Papadimitriou, Christos H. (1987), "The 1-Steiner tree problem", Journal of Algorithms, 8 (1): 122–130, doi:10.1016/0196-6774(87)90032-0, MR 0875330
↑ ^{Jump up to: 15.0} ^15.1 Robins, G.; Salowe, J. S. (1995), "Low-degree minimum spanning trees", Discrete & Computational Geometry, 14 (2): 151–165, doi:10.1007/BF02570700, MR 1331924, S2CID 16040977
↑ Pfender, Florian; Ziegler, Günter M. (September 2004), "Kissing numbers, sphere packings, and some unexpected proofs" (PDF), Notices of the American Mathematical Society: 873–883
↑ Steele, J. Michael; Shepp, Lawrence A.; Eddy, William F. (1987), "On the number of leaves of a Euclidean minimal spanning tree", Journal of Applied Probability, 24 (4): 809–826, doi:10.2307/3214207, JSTOR 3214207, MR 0913823, S2CID 29026025
↑ Preparata, Franco P.; Shamos, Michael Ian (1985), Computational Geometry: An Introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York, p. 263, doi:10.1007/978-1-4612-1098-6, ISBN 0-387-96131-3, MR 0805539, S2CID 206656565
↑ Toussaint, G. T. (1980), "Comment: Algorithms for computing relative neighborhood graph", Electronics Letters, 16 (22): 860, Bibcode:1980ElL....16..860T, doi:10.1049/el:19800611; reply by Urquhart, pp. 860–861
↑ ^{Jump up to: 20.0} ^20.1 ^20.2 Yao, Andrew Chi Chih (1982), "On constructing minimum spanning trees in $k$ -dimensional spaces and related problems", SIAM Journal on Computing, 11 (4): 721–736, doi:10.1137/0211059, MR 0677663
↑ ^{Jump up to: 21.0} ^21.1 Bentley, Jon Louis; Weide, Bruce W.; Yao, Andrew C. (1980), "Optimal expected-time algorithms for closest point problems", ACM Transactions on Mathematical Software, 6 (4): 563–580, doi:10.1145/355921.355927, MR 0599977, S2CID 17238717
↑ Steele, J. Michael; Snyder, Timothy Law (1989), "Worst-case growth rates of some classical problems of combinatorial optimization", SIAM Journal on Computing, 18 (2): 278–287, doi:10.1137/0218019, MR 0986667
↑ Steele, J. Michael (1988), "Growth rates of Euclidean minimal spanning trees with power weighted edges", Annals of Probability, 16 (4): 1767–1787, doi:10.1214/aop/1176991596, JSTOR 2243991, MR 0958215
↑ Penrose, Mathew D. (1997), "The longest edge of the random minimal spanning tree", The Annals of Applied Probability, 7 (2): 340–361, doi:10.1214/aoap/1034625335, MR 1442317
↑ Boyce, W. M.; Garey, M. R.; Johnson, D. S. (1978), "A note on bisecting minimum spanning trees", Networks, 8 (3): 187–192, doi:10.1002/net.3230080302, MR 0491324
↑ ^{Jump up to: 26.0} ^26.1 ^26.2 Buchin, Kevin; Mulzer, Wolfgang (2011), "Delaunay triangulations in $O$ (sort( $n$ )) time and more", Journal of the ACM, 58 (2): A6:1–A6:27, doi:10.1145/1944345.1944347, MR 2786587, S2CID 11316974
↑ Mareš, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes" (PDF), Archivum Mathematicum, 40 (3): 315–320, MR 2107027
↑ Devillers, Olivier (1992), "Randomization yields simple $O (n log * n)$ [[Category: Templates Vigyan Ready]] algorithms for difficult $Ω(n)$ [[Category: Templates Vigyan Ready]] problems" (PDF), International Journal of Computational Geometry & Applications, 2 (1): 97–111, doi:10.1142/S021819599200007X, MR 1159844, S2CID 60203 {{citation}}: URL–wikilink conflict (help)
↑ O'Rourke, J.; Demaine, E. (2001–2002), "Problem 5: Euclidean Minimum Spanning Tree", The Open Problems Project, Smith College
↑ Dwyer, Rex A. (1991), "Higher-dimensional Voronoi diagrams in linear expected time", Discrete & Computational Geometry, 6 (4): 343–367, doi:10.1007/BF02574694, MR 1098813
↑ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the ACM, 42 (2): 321–328, doi:10.1145/201019.201022, MR 1409738, S2CID 832583
↑ Chatterjee, S.; Connor, M.; Kumar, P. (2010), "Geometric minimum spanning trees with GeoFilterKruskal", in Festa, Paola (ed.), Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010, Proceedings, Lecture Notes in Computer Science, vol. 6049, Springer-Verlag, pp. 486–500, doi:10.1007/978-3-642-13193-6_41
↑ Arya, Sunil; Mount, David M. (2016), "A fast and simple algorithm for computing approximate Euclidean minimum spanning trees", in Krauthgamer, Robert (ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 1220–1233, doi:10.1137/1.9781611974331.ch85, MR 3478461
↑ Eppstein, David (1994), "Offline algorithms for dynamic minimum spanning tree problems", Journal of Algorithms, 17 (2): 237–250, doi:10.1006/jagm.1994.1033, MR 1291541
↑ Chan, Timothy M. (2010), "A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries", Journal of the ACM, 57 (3): Article 16, doi:10.1145/1706591.1706596, MR 2665885, S2CID 47454142
↑ Eppstein, David (1995), "Dynamic Euclidean minimum spanning trees and extrema of binary functions", Discrete & Computational Geometry, 13 (1): 111–122, doi:10.1007/BF02574030, MR 1300511, S2CID 7339165
↑ Katoh, N.; Tokuyama, T.; Iwano, K. (1995), "On minimum and maximum spanning trees of linearly moving points", Discrete & Computational Geometry, 13 (2): 161–176, doi:10.1007/BF02574035, MR 1314960
↑ Chan, Timothy M. (2003), "On levels in arrangements of curves", Discrete & Computational Geometry, 29 (3): 375–393, doi:10.1007/s00454-002-2840-2, MR 1961005, S2CID 18966889
↑ Rahmati, Zahed; Zarei, Alireza (2010), "Combinatorial changes of Euclidean minimum spanning tree of moving points in the plane" (PDF), Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, Winnipeg, Manitoba, Canada, August 9-11, 2010, pp. 43–45
↑ Akitaya, Hugo A.; Biniaz, Ahmad; Bose, Prosenjit; De Carufel, Jean-Lou; Maheshwari, Anil; da Silveira, Luís Fernando Schultz Xavier; Smid, Michiel (2021), "The minimum moving spanning tree problem", in Lubiw, Anna; Salavatipour, Mohammad R. (eds.), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12808, Springer, pp. 15–28, doi:10.1007/978-3-030-83508-8_2, S2CID 234599877
↑ Basch, Julien; Guibas, Leonidas J.; Zhang, Li (1997), "Proximity problems on moving points", in Boissonnat, Jean-Daniel (ed.), Proceedings of the Thirteenth Annual Symposium on Computational Geometry, Nice, France, June 4–6, 1997, Association for Computing Machinery, pp. 344–351, doi:10.1145/262839.262998, S2CID 15556637
↑ Agarwal, Pankaj K.; Eppstein, David; Guibas, Leonidas J.; Henzinger, Monika Rauch (1998), "Parametric and Kinetic Minimum Spanning Trees", 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8–11, 1998, Palo Alto, California, USA (PDF), IEEE Computer Society, pp. 596–605, doi:10.1109/SFCS.1998.743510, S2CID 2559456
↑ Rahmati, Zahed; Zarei, Alireza (2012), "Kinetic Euclidean minimum spanning tree in the plane", Journal of Discrete Algorithms, 16: 2–11, doi:10.1016/j.jda.2012.04.009, MR 2960341
↑ ^{Jump up to: 44.0} ^44.1 Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue; Zarei, Alireza (2015), "A simple, faster method for kinetic proximity problems", Computational Geometry: Theory & Applications, 48 (4): 342–359, doi:10.1016/j.comgeo.2014.12.002, MR 3296072, S2CID 18971251
↑ Meulemans, Wouter; Speckmann, Bettina; Verbeek, Kevin; Wulms, Jules (2018), "A framework for algorithm stability and its application to kinetic Euclidean MSTs", in Bender, Michael A.; Farach-Colton, Martin; Mosteiro, Miguel A. (eds.), LATIN 2018: Theoretical Informatics – 13th Latin American Symposium, Buenos Aires, Argentina, April 16–19, 2018, Proceedings, Lecture Notes in Computer Science, vol. 10807, Springer, pp. 805–819, doi:10.1007/978-3-319-77404-6_58, S2CID 4709616
↑ Yao, Andrew Chi-Chih (1991), "Lower bounds for algebraic computation trees with integer inputs", SIAM Journal on Computing, 20 (4): 655–668, doi:10.1137/0220041, MR 1105929
↑ Graham, R. L.; Hell, Pavol (1985), "On the history of the minimum spanning tree problem", IEEE Annals of the History of Computing, 7 (1): 43–57, doi:10.1109/mahc.1985.10011, MR 0783327, S2CID 10555375
↑ Loberman, H.; Weinberger, A. (October 1957), "Formal procedures for connecting terminals with a minimum total wire length", Journal of the ACM, 4 (4): 428–437, doi:10.1145/320893.320896, S2CID 7320964
↑ Wu, Bin; Yu, Bailang; Wu, Qiusheng; Chen, Zuoqi; Yao, Shenjun; Huang, Yan; Wu, Jianping (October 2017), "An extended minimum spanning tree method for characterizing local urban patterns", International Journal of Geographical Information Science, 32 (3): 450–475, doi:10.1080/13658816.2017.1384830, S2CID 46772272
↑ Zahn, C. T. (1973), "Using the minimum spanning tree to recognize dotted and dashed curves", 1st International Computing Symposium, Davos, Switzerland, 4–7 September 1973
↑ Lee, In-Kwon (2000), "Curve reconstruction from unorganized points", Computer Aided Geometric Design, 17 (2): 161–177, doi:10.1016/S0167-8396(99)00044-8, MR 1733203
↑ Bartal, Yair; Gottlieb, Lee-Ad (2013), "A linear time approximation scheme for Euclidean TSP", 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pp. 698–706, doi:10.1109/FOCS.2013.80, MR 3246273, S2CID 17514182
↑ Wan, P.-J.; Călinescu, G.; Li, X.-Y.; Frieder, O. (2002), "Minimum-energy broadcasting in static ad hoc wireless networks", Wireless Networks, 8 (6): 607–617, doi:10.1023/a:1020381720601, S2CID 1297518
↑ Clementi, Andrea E. F.; Huiban, Gurvan; Rossi, Gianluca; Verhoeven, Yann C.; Penna, Paolo (2003), "On the approximation ratio of the MST-based heuristic for the energy-efficient broadcast problem in static ad-hoc radio networks", 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 22-26 April 2003, Nice, France, Proceedings, IEEE Computer Society, p. 222, doi:10.1109/IPDPS.2003.1213407, S2CID 17863487
↑ Flammini, Michele; Klasing, Ralf; Navarra, Alfredo; Perennes, Stephane (2007), "Improved approximation results for the minimum energy broadcasting problem", Algorithmica, 49 (4): 318–336, doi:10.1007/s00453-007-9077-7, MR 2358524, S2CID 11982404
↑ Ambühl, Christoph (2005), "An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks", in Caires, Luís; Italiano, Giuseppe F.; Monteiro, Luís; Palamidessi, Catuscia; Yung, Moti (eds.), Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3580, Springer, pp. 1139–1150, doi:10.1007/11523468_92
↑ Eades, Peter; Whitesides, Sue (1996), "The realization problem for Euclidean minimum spanning trees is NP-hard", Algorithmica, 16 (1): 60–82, doi:10.1007/s004539900037, MR 1394494
↑ Angelini, Patrizio; Bruckdorfer, Till; Chiesa, Marco; Frati, Fabrizio; Kaufmann, Michael; Squarcella, Claudio (2014), "On the area requirements of Euclidean minimum spanning trees", Computational Geometry: Theory and Applications, 47 (2, part B): 200–213, doi:10.1016/j.comgeo.2012.10.011, MR 3123788

बाहरी संबंध

EMST tutorial, mlpack documentation

[gowros-1] {Jump up to: 1.0} ^1.1 Gower, J. C.; Ross, G. J. S. (1969), "Minimum spanning trees and single linkage cluster analysis", Applied Statistics, 18 (1): 54–61, doi:10.2307/2346439, JSTOR 2346439, MR 0242315

[shahoe-2] {Jump up to: 2.0} ^2.1 ^2.2 ^2.3 Shamos, Michael Ian; Hoey, Dan (1975), "Closest-point problems", 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, IEEE Computer Society, pp. 151–162, doi:10.1109/SFCS.1975.8, MR 0426498, S2CID 40615455

[bdek-3] Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David (2006), "On the spanning ratio of Gabriel graphs and β-skeletons", SIAM Journal on Discrete Mathematics, 20 (2): 412–427, doi:10.1137/S0895480197318088, MR 2257270

[aesw-4] {Jump up to: 4.0} ^4.1 ^4.2 ^4.3 Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O.; Welzl, E. (1991), "Euclidean minimum spanning trees and bichromatic closest pairs", Discrete & Computational Geometry, Springer, 6 (1): 407–422, doi:10.1007/BF02574698, MR 1115099

[mrg-5] {Jump up to: 5.0} ^5.1 ^5.2 March, William B.; Ram, Parikshit; Gray, Alexander G. (2010), "Fast Euclidean minimum spanning tree: algorithm, analysis, and applications", in Rao, Bharat; Krishnapuram, Balaji; Tomkins, Andrew; Yang, Qiang (eds.), Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010, pp. 603–612, doi:10.1145/1835804.1835882, S2CID 186025

[clarkson-6] {Jump up to: 6.0} ^6.1 Clarkson, Kenneth L. (1989), "An algorithm for geometric minimum spanning trees requiring nearly linear expected time", Algorithmica, 4 (1–4): 461–469, doi:10.1007/BF01553902, MR 1019387, S2CID 22176641

[monsur-7] {Jump up to: 7.0} ^7.1 ^7.2 ^7.3 Monma, Clyde; Suri, Subhash (1992), "Transitions in geometric minimum spanning trees", Discrete & Computational Geometry, 8 (3): 265–293, doi:10.1007/BF02293049, MR 1174358, S2CID 30101649

[nzz-8] {Jump up to: 8.0} ^8.1 Narasimhan, Giri; Zachariasen, Martin; Zhu, Jianlin (2000), "Experiments with computing geometric minimum spanning trees", Proceedings of the 2nd Workshop on Algorithm Engineering and Experiments, pp. 183–196

[frakau-9] {Jump up to: 9.0} ^9.1 Frati, Fabrizio; Kaufmann, Michael (2011), "Polynomial area bounds for MST embeddings of trees", Computational Geometry: Theory and Applications, 44 (9): 529–543, doi:10.1016/j.comgeo.2011.05.005, MR 2819643, S2CID 5634139

[king-10] {Jump up to: 10.0} ^10.1 King, James A. (2006), "Realization of degree 10 minimum spanning trees in 3-space" (PDF), Proceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006, August 14-16, 2006, Queen's University, Ontario, Canada, pp. 39–42

[kln-11] {Jump up to: 11.0} ^11.1 Krznaric, Drago; Levcopoulos, Christos; Nilsson, Bengt J. (1999), "Minimum spanning trees in $d$ dimensions", Nordic Journal of Computing, 6 (4): 446–461, MR 1736451. 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.

[gilpol-12] {Jump up to: 12.0} ^12.1 ^12.2 ^12.3 ^12.4 ^12.5 ^12.6 Gilbert, E. N.; Pollak, H. O. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400, MR 0223269

[eppstein-13] {Jump up to: 13.0} ^13.1 ^13.2 ^13.3 Eppstein, David (1999), "Spanning trees and spanners" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425–461, MR 1746681

[1steiner-14] Georgakopoulos, George; Papadimitriou, Christos H. (1987), "The 1-Steiner tree problem", Journal of Algorithms, 8 (1): 122–130, doi:10.1016/0196-6774(87)90032-0, MR 0875330

[robsal-15] {Jump up to: 15.0} ^15.1 Robins, G.; Salowe, J. S. (1995), "Low-degree minimum spanning trees", Discrete & Computational Geometry, 14 (2): 151–165, doi:10.1007/BF02570700, MR 1331924, S2CID 16040977

[kissing-16] Pfender, Florian; Ziegler, Günter M. (September 2004), "Kissing numbers, sphere packings, and some unexpected proofs" (PDF), Notices of the American Mathematical Society: 873–883

[sse-17] Steele, J. Michael; Shepp, Lawrence A.; Eddy, William F. (1987), "On the number of leaves of a Euclidean minimal spanning tree", Journal of Applied Probability, 24 (4): 809–826, doi:10.2307/3214207, JSTOR 3214207, MR 0913823, S2CID 29026025

[presha-18] Preparata, Franco P.; Shamos, Michael Ian (1985), Computational Geometry: An Introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York, p. 263, doi:10.1007/978-1-4612-1098-6, ISBN 0-387-96131-3, MR 0805539, S2CID 206656565

[comment-19] Toussaint, G. T. (1980), "Comment: Algorithms for computing relative neighborhood graph", Electronics Letters, 16 (22): 860, Bibcode:1980ElL....16..860T, doi:10.1049/el:19800611; reply by Urquhart, pp. 860–861

[yao82-20] {Jump up to: 20.0} ^20.1 ^20.2 Yao, Andrew Chi Chih (1982), "On constructing minimum spanning trees in $k$ -dimensional spaces and related problems", SIAM Journal on Computing, 11 (4): 721–736, doi:10.1137/0211059, MR 0677663

[bwy-21] {Jump up to: 21.0} ^21.1 Bentley, Jon Louis; Weide, Bruce W.; Yao, Andrew C. (1980), "Optimal expected-time algorithms for closest point problems", ACM Transactions on Mathematical Software, 6 (4): 563–580, doi:10.1145/355921.355927, MR 0599977, S2CID 17238717

[ss89-22] Steele, J. Michael; Snyder, Timothy Law (1989), "Worst-case growth rates of some classical problems of combinatorial optimization", SIAM Journal on Computing, 18 (2): 278–287, doi:10.1137/0218019, MR 0986667

[steele-23] Steele, J. Michael (1988), "Growth rates of Euclidean minimal spanning trees with power weighted edges", Annals of Probability, 16 (4): 1767–1787, doi:10.1214/aop/1176991596, JSTOR 2243991, MR 0958215

[penrose-24] Penrose, Mathew D. (1997), "The longest edge of the random minimal spanning tree", The Annals of Applied Probability, 7 (2): 340–361, doi:10.1214/aoap/1034625335, MR 1442317

[bgj78-25] Boyce, W. M.; Garey, M. R.; Johnson, D. S. (1978), "A note on bisecting minimum spanning trees", Networks, 8 (3): 187–192, doi:10.1002/net.3230080302, MR 0491324

[bm09-26] {Jump up to: 26.0} ^26.1 ^26.2 Buchin, Kevin; Mulzer, Wolfgang (2011), "Delaunay triangulations in $O$ (sort( $n$ )) time and more", Journal of the ACM, 58 (2): A6:1–A6:27, doi:10.1145/1944345.1944347, MR 2786587, S2CID 11316974

[mares-27] Mareš, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes" (PDF), Archivum Mathematicum, 40 (3): 315–320, MR 2107027

[devillers-28] Devillers, Olivier (1992), "Randomization yields simple $O (n log * n)$ [[Category: Templates Vigyan Ready]] algorithms for difficult $Ω(n)$ [[Category: Templates Vigyan Ready]] problems" (PDF), International Journal of Computational Geometry & Applications, 2 (1): 97–111, doi:10.1142/S021819599200007X, MR 1159844, S2CID 60203 {{citation}}: URL–wikilink conflict (help)

[topp-29] O'Rourke, J.; Demaine, E. (2001–2002), "Problem 5: Euclidean Minimum Spanning Tree", The Open Problems Project, Smith College

[dwyer-30] Dwyer, Rex A. (1991), "Higher-dimensional Voronoi diagrams in linear expected time", Discrete & Computational Geometry, 6 (4): 343–367, doi:10.1007/BF02574694, MR 1098813

[kkt-31] Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the ACM, 42 (2): 321–328, doi:10.1145/201019.201022, MR 1409738, S2CID 832583

[cck-32] Chatterjee, S.; Connor, M.; Kumar, P. (2010), "Geometric minimum spanning trees with GeoFilterKruskal", in Festa, Paola (ed.), Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010, Proceedings, Lecture Notes in Computer Science, vol. 6049, Springer-Verlag, pp. 486–500, doi:10.1007/978-3-642-13193-6_41

[arymou-33] Arya, Sunil; Mount, David M. (2016), "A fast and simple algorithm for computing approximate Euclidean minimum spanning trees", in Krauthgamer, Robert (ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 1220–1233, doi:10.1137/1.9781611974331.ch85, MR 3478461

[offline-34] Eppstein, David (1994), "Offline algorithms for dynamic minimum spanning tree problems", Journal of Algorithms, 17 (2): 237–250, doi:10.1006/jagm.1994.1033, MR 1291541

[chadyn-35] Chan, Timothy M. (2010), "A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries", Journal of the ACM, 57 (3): Article 16, doi:10.1145/1706591.1706596, MR 2665885, S2CID 47454142

[extrema-36] Eppstein, David (1995), "Dynamic Euclidean minimum spanning trees and extrema of binary functions", Discrete & Computational Geometry, 13 (1): 111–122, doi:10.1007/BF02574030, MR 1300511, S2CID 7339165

[kti-37] Katoh, N.; Tokuyama, T.; Iwano, K. (1995), "On minimum and maximum spanning trees of linearly moving points", Discrete & Computational Geometry, 13 (2): 161–176, doi:10.1007/BF02574035, MR 1314960

[chalev-38] Chan, Timothy M. (2003), "On levels in arrangements of curves", Discrete & Computational Geometry, 29 (3): 375–393, doi:10.1007/s00454-002-2840-2, MR 1961005, S2CID 18966889

[rzcomb-39] Rahmati, Zahed; Zarei, Alireza (2010), "Combinatorial changes of Euclidean minimum spanning tree of moving points in the plane" (PDF), Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, Winnipeg, Manitoba, Canada, August 9-11, 2010, pp. 43–45

[abb-40] Akitaya, Hugo A.; Biniaz, Ahmad; Bose, Prosenjit; De Carufel, Jean-Lou; Maheshwari, Anil; da Silveira, Luís Fernando Schultz Xavier; Smid, Michiel (2021), "The minimum moving spanning tree problem", in Lubiw, Anna; Salavatipour, Mohammad R. (eds.), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12808, Springer, pp. 15–28, doi:10.1007/978-3-030-83508-8_2, S2CID 234599877

[bgz-41] Basch, Julien; Guibas, Leonidas J.; Zhang, Li (1997), "Proximity problems on moving points", in Boissonnat, Jean-Daniel (ed.), Proceedings of the Thirteenth Annual Symposium on Computational Geometry, Nice, France, June 4–6, 1997, Association for Computing Machinery, pp. 344–351, doi:10.1145/262839.262998, S2CID 15556637

[aegh-42] Agarwal, Pankaj K.; Eppstein, David; Guibas, Leonidas J.; Henzinger, Monika Rauch (1998), "Parametric and Kinetic Minimum Spanning Trees", 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8–11, 1998, Palo Alto, California, USA (PDF), IEEE Computer Society, pp. 596–605, doi:10.1109/SFCS.1998.743510, S2CID 2559456

[rzkin-43] Rahmati, Zahed; Zarei, Alireza (2012), "Kinetic Euclidean minimum spanning tree in the plane", Journal of Discrete Algorithms, 16: 2–11, doi:10.1016/j.jda.2012.04.009, MR 2960341

[rakwz-44] {Jump up to: 44.0} ^44.1 Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue; Zarei, Alireza (2015), "A simple, faster method for kinetic proximity problems", Computational Geometry: Theory & Applications, 48 (4): 342–359, doi:10.1016/j.comgeo.2014.12.002, MR 3296072, S2CID 18971251

[msvw-45] Meulemans, Wouter; Speckmann, Bettina; Verbeek, Kevin; Wulms, Jules (2018), "A framework for algorithm stability and its application to kinetic Euclidean MSTs", in Bender, Michael A.; Farach-Colton, Martin; Mosteiro, Miguel A. (eds.), LATIN 2018: Theoretical Informatics – 13th Latin American Symposium, Buenos Aires, Argentina, April 16–19, 2018, Proceedings, Lecture Notes in Computer Science, vol. 10807, Springer, pp. 805–819, doi:10.1007/978-3-319-77404-6_58, S2CID 4709616

[yao89-46] Yao, Andrew Chi-Chih (1991), "Lower bounds for algebraic computation trees with integer inputs", SIAM Journal on Computing, 20 (4): 655–668, doi:10.1137/0220041, MR 1105929

[history-47] Graham, R. L.; Hell, Pavol (1985), "On the history of the minimum spanning tree problem", IEEE Annals of the History of Computing, 7 (1): 43–57, doi:10.1109/mahc.1985.10011, MR 0783327, S2CID 10555375

[lobwei-48] Loberman, H.; Weinberger, A. (October 1957), "Formal procedures for connecting terminals with a minimum total wire length", Journal of the ACM, 4 (4): 428–437, doi:10.1145/320893.320896, S2CID 7320964

[urban-49] Wu, Bin; Yu, Bailang; Wu, Qiusheng; Chen, Zuoqi; Yao, Shenjun; Huang, Yan; Wu, Jianping (October 2017), "An extended minimum spanning tree method for characterizing local urban patterns", International Journal of Geographical Information Science, 32 (3): 450–475, doi:10.1080/13658816.2017.1384830, S2CID 46772272

[zahn-50] Zahn, C. T. (1973), "Using the minimum spanning tree to recognize dotted and dashed curves", 1st International Computing Symposium, Davos, Switzerland, 4–7 September 1973

[lee-51] Lee, In-Kwon (2000), "Curve reconstruction from unorganized points", Computer Aided Geometric Design, 17 (2): 161–177, doi:10.1016/S0167-8396(99)00044-8, MR 1733203

[bargot-52] Bartal, Yair; Gottlieb, Lee-Ad (2013), "A linear time approximation scheme for Euclidean TSP", 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pp. 698–706, doi:10.1109/FOCS.2013.80, MR 3246273, S2CID 17514182

[wclf-53] Wan, P.-J.; Călinescu, G.; Li, X.-Y.; Frieder, O. (2002), "Minimum-energy broadcasting in static ad hoc wireless networks", Wireless Networks, 8 (6): 607–617, doi:10.1023/a:1020381720601, S2CID 1297518

[chrvp-54] Clementi, Andrea E. F.; Huiban, Gurvan; Rossi, Gianluca; Verhoeven, Yann C.; Penna, Paolo (2003), "On the approximation ratio of the MST-based heuristic for the energy-efficient broadcast problem in static ad-hoc radio networks", 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 22-26 April 2003, Nice, France, Proceedings, IEEE Computer Society, p. 222, doi:10.1109/IPDPS.2003.1213407, S2CID 17863487

[fknp-55] Flammini, Michele; Klasing, Ralf; Navarra, Alfredo; Perennes, Stephane (2007), "Improved approximation results for the minimum energy broadcasting problem", Algorithmica, 49 (4): 318–336, doi:10.1007/s00453-007-9077-7, MR 2358524, S2CID 11982404

[ambuhl-56] Ambühl, Christoph (2005), "An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks", in Caires, Luís; Italiano, Giuseppe F.; Monteiro, Luís; Palamidessi, Catuscia; Yung, Moti (eds.), Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3580, Springer, pp. 1139–1150, doi:10.1007/11523468_92

[ew94-57] Eades, Peter; Whitesides, Sue (1996), "The realization problem for Euclidean minimum spanning trees is NP-hard", Algorithmica, 16 (1): 60–82, doi:10.1007/s004539900037, MR 1394494

[abcfks-58] Angelini, Patrizio; Bruckdorfer, Till; Chiesa, Marco; Frati, Fabrizio; Kaufmann, Michael; Squarcella, Claudio (2014), "On the area requirements of Euclidean minimum spanning trees", Computational Geometry: Theory and Applications, 47 (2, part B): 200–213, doi:10.1016/j.comgeo.2012.10.011, MR 3123788

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

Anonymous

Search

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

Namespaces

More

Page actions

Contents

परिभाषा और संबंधित समस्याएँ

गुण

कोण और शीर्ष डिग्री

रिक्त क्षेत्र

सुपरग्राफ

कुल लंबाई

उपखंड

कम्प्यूटेशनल जटिलता

दो आयाम

उच्च आयाम

गतिशील और गतिज(काइनेटिक)

निचली सीमा

अनुप्रयोग

प्रतीति

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

परिभाषा और संबंधित समस्याएँ

गुण

कोण और शीर्ष डिग्री

रिक्त क्षेत्र

सुपरग्राफ

कुल लंबाई

उपखंड

कम्प्यूटेशनल जटिलता

दो आयाम

उच्च आयाम

गतिशील और गतिज(काइनेटिक)

निचली सीमा

अनुप्रयोग

प्रतीति

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories