सीमा क्षेत्र: Difference between revisions

Revision as of 11:12, 27 April 2023

सबसे छोटे सीमक वृत्त के कुछ उदाहरण, 2 आयामों में सीमक गोले की स्थिति।

गणित में, $d$ आयामी स्थान परिमित विस्तार की वस्तुओं का एक गैर-रिक्त समुच्चय दिया गया है , उदाहरण के लिए बिंदुओं का समुच्चय, एक सीमक क्षेत्र, परिबद्ध क्षेत्र या परिबद्ध गेंद उस समुच्चय के लिए $d$ आयामी ठोस गोला है जिसमें ये सभी वस्तुएं होती हैं।

कंप्यूटर चित्रलेख और कम्प्यूटेशनल ज्यामिति में प्रयुक्त, सीमक क्षेत्र एक विशेष प्रकार की सीमक मात्रा है। वास्तविक समय के कंप्यूटर चित्रलेख अनुप्रयोगों में उच्च व्यावहारिक मान के साथ कई तीव्र और सरल सीमक क्षेत्र निर्माण एल्गोरिदम हैं।^[1]

सांख्यिकी और संचालन अनुसंधान में, वस्तुएं सामान्यतः बिंदु होती हैं, और सामान्यतः ब्याज का क्षेत्र न्यूनतम सीमा क्षेत्र होता है, अर्थात, सभी सीमा क्षेत्रों के बीच न्यूनतम त्रिज्या वाला क्षेत्र। यह सिद्ध किया जा सकता है कि ऐसा क्षेत्र अद्वितीय है: यदि उनमें से दो हैं, तो विचाराधीन वस्तुएँ उनके प्रतिच्छेदन के भीतर स्थित हैं। परन्तु समान त्रिज्या वाले दो असंपाती गोलों का प्रतिच्छेदन छोटे त्रिज्या वाले गोले में निहित होते है।

न्यूनतम सीमक गोले के केंद्र की गणना करने की समस्या को भारित यूक्लिडियन 1-केंद्र समस्या के रूप में भी जाना जाता है।

अनुप्रयोग

गुच्छन

गुच्छ विश्लेषण में ऐसे क्षेत्र उपयोगी होते हैं, जहां समान डेटा बिंदुओं के समूहों को एक साथ वर्गीकृत किया जाता है।

सांख्यिकीय विश्लेषण में क्षेत्र के भीतर डेटा बिंदुओं के प्रकीर्णन (आँकड़े) को माप त्रुटि या प्राकृतिक (सामान्यतः ऊष्मा ) प्रक्रियाओं के लिए उत्तरदायी ठहराया जा सकता है, इस स्थिति में गुच्छ एक आदर्श बिंदु के क्षोभ का प्रतिनिधित्व करता है। कुछ परिस्थितियों में इस आदर्श बिंदु का उपयोग गुच्छ में बिंदुओं के विकल्प के रूप में किया जा सकता है, जो गणना समय को कम करने में लाभप्रद है।

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

एल्गोरिदम

सीमक क्षेत्र समस्या को हल करने के लिए यथार्थ और अनुमानित एल्गोरिदम हैं।

रैखिक प्रोग्रामन

निम्रोद मगिद्दो ने 1-केंद्र समस्या का बड़े पैमाने पर अध्ययन किया और 1980 के दशक में कम से कम पांच बार इस पर प्रकाशित किया।^[2] 1983 में, उन्होंने छँटाई और खोज एल्गोरिदम का प्रस्ताव किया जो इष्टतम सीमक क्षेत्र को खोजता है और रैखिक समय में चलता है यदि आयाम एक स्थिर के रूप में निर्धारित किया गया है। जब आयाम $d$ को ध्यान में रखा जाता है, तो निष्पादन समय जटिलता $O(2^{O(d^{2})}n)$ होती है,^[3]^[4] जो उच्च-आयामी अनुप्रयोगों के लिए अव्यावहारिक है।

1991 में, इमो वेलज़ल ने रायमुंड सीडेल द्वारा एक यादृच्छिक रैखिक प्रोग्रामन एल्गोरिदम को सामान्य करते हुए, एक बहुत ही सरल यादृच्छिक एल्गोरिदम का प्रस्ताव दिया। वेलज़ल के एल्गोरिदम का अपेक्षित चलने का समय $O((d+1)(d+1)!n)$ है, जो फिर से किसी निश्चित आयाम $d$ के लिए $O(n)$ में कम हो जाते है। लेख्य उच्च आयामों में इसकी व्यावहारिकता को प्रदर्शित करते हुए प्रायोगिक परिणाम प्रदान करते है।^[5] टिमोथी चान का एक और वर्तमान नियतात्मक एल्गोरिदम भी आयाम पर कम (परन्तु अभी भी घातीय) निर्भरता के साथ, $O(n)$ समय में चलते है।^[4]

ओपन-सोर्स कम्प्यूटेशनल ज्यामिति एल्गोरिदम लाइब्रेरी (सीजीएएल) में वेल्ज़ल के एल्गोरिदम का कार्यान्वयन सम्मिलित है।^[6]

रिटर का सीमक क्षेत्र

1990 में, जैक रिटर ने गैर-न्यूनतम सीमक क्षेत्र खोजने के लिए सरल एल्गोरिदम प्रस्तावित किया।^[7] इसकी सादगी के लिए इसका व्यापक रूप से विभिन्न अनुप्रयोगों में उपयोग किया जाता है। एल्गोरिदम इस प्रकार काम करता है:

$P$ से एक बिंदु $x$ चुनें, $P$ में एक बिंदु $y$ खोजें, जिसकी $x$ से सबसे बड़ी दूरी हो;
$P$ में एक बिंदु $z$ खोजें, जिसकी $y$ से सबसे बड़ी दूरी हो। $y$ और $z$ के मध्य बिंदु के रूप में इसके केंद्र के साथ एक प्रारंभिक गेंद $B$ समूहित करें , $y$ और $z$ के बीच की दूरी के आधे के रूप में त्रिज्या;
यदि $P$ में सभी बिंदु गेंद $B$ के भीतर हैं , तब हमें एक परिबद्ध गोला मिलता है। अन्यथा, $p$ को गेंद के बाहर एक बिंदु होने दें, बिंदु $p$ और पिछली गेंद दोनों को आच्छादन करते हुए नवीन गेंद का निर्माण करें। इस चरण को तब तक दोहराएं जब तक कि सभी बिंदु आच्छादित न हो जाएं।

रिटर का एल्गोरिदम $d$ -आयामी स्थान में $n$ बिन्दु वाले निविष्ट पर समय

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
 {{Short description|Sphere that contains a set of objects}}
 {{for|the planar problem|सीमक वृत्त}}
-[[Image:Smallest circle problem.svg|thumb|right|300px|सबसे छोटे सीमक वृत्त के कुछ उदाहरण, 2 आयामों में सीमक गोले की स्थिति।]]गणित में, <math>d</math> आयामी स्थान परिमित विस्तार की वस्तुओं का एक गैर-रिक्त समुच्चय दिया गया है , उदाहरण के लिए बिंदुओं का एक समुच्चय, एक सीमक क्षेत्र, परिबद्ध क्षेत्र या परिबद्ध गेंद उस समुच्चय के लिए <math>d</math> आयामी [[ठोस गोला]] है जिसमें ये सभी वस्तुएं होती हैं।
+[[Image:Smallest circle problem.svg|thumb|right|300px|सबसे छोटे सीमक वृत्त के कुछ उदाहरण, 2 आयामों में सीमक गोले की स्थिति।]]गणित में, <math>d</math> आयामी स्थान परिमित विस्तार की वस्तुओं का एक गैर-रिक्त समुच्चय दिया गया है , उदाहरण के लिए बिंदुओं का समुच्चय, एक सीमक क्षेत्र, परिबद्ध क्षेत्र या परिबद्ध गेंद उस समुच्चय के लिए <math>d</math> आयामी [[ठोस गोला]] है जिसमें ये सभी वस्तुएं होती हैं।
-[[कंप्यूटर चित्रलेख]] और [[कम्प्यूटेशनल ज्यामिति]] में प्रयुक्त, एक सीमक क्षेत्र एक विशेष प्रकार की [[बाउंडिंग वॉल्यूम|सीमक मात्रा]] है। वास्तविक समय के कंप्यूटर चित्रलेख अनुप्रयोगों में उच्च व्यावहारिक मान के साथ कई तीव्र और सरल सीमक क्षेत्र निर्माण एल्गोरिदम हैं।{{r|epos}}
+[[कंप्यूटर चित्रलेख]] और [[कम्प्यूटेशनल ज्यामिति]] में प्रयुक्त, सीमक क्षेत्र एक विशेष प्रकार की [[बाउंडिंग वॉल्यूम|सीमक मात्रा]] है। वास्तविक समय के कंप्यूटर चित्रलेख अनुप्रयोगों में उच्च व्यावहारिक मान के साथ कई तीव्र और सरल सीमक क्षेत्र निर्माण एल्गोरिदम हैं।{{r|epos}}
-सांख्यिकी और संचालन अनुसंधान में, वस्तुएं सामान्यतः बिंदु होती हैं, और सामान्यतः ब्याज का क्षेत्र न्यूनतम सीमा क्षेत्र होता है, अर्थात, सभी सीमा क्षेत्रों के बीच न्यूनतम त्रिज्या वाला क्षेत्र। यह सिद्ध किया जा सकता है कि ऐसा क्षेत्र अद्वितीय है: यदि उनमें से दो हैं, तो विचाराधीन वस्तुएँ उनके प्रतिच्छेदन के भीतर स्थित हैं। परन्तु समान त्रिज्या वाले दो असंपाती गोलों का प्रतिच्छेदन छोटे त्रिज्या वाले गोले में निहित होता है।
+सांख्यिकी और संचालन अनुसंधान में, वस्तुएं सामान्यतः बिंदु होती हैं, और सामान्यतः ब्याज का क्षेत्र न्यूनतम सीमा क्षेत्र होता है, अर्थात, सभी सीमा क्षेत्रों के बीच न्यूनतम त्रिज्या वाला क्षेत्र। यह सिद्ध किया जा सकता है कि ऐसा क्षेत्र अद्वितीय है: यदि उनमें से दो हैं, तो विचाराधीन वस्तुएँ उनके प्रतिच्छेदन के भीतर स्थित हैं। परन्तु समान त्रिज्या वाले दो असंपाती गोलों का प्रतिच्छेदन छोटे त्रिज्या वाले गोले में निहित होते है।
 न्यूनतम सीमक गोले के केंद्र की गणना करने की समस्या को भारित यूक्लिडियन [[1-केंद्र समस्या]] के रूप में भी जाना जाता है।
@@ Line 14: / Line 14: @@
 [[क्लस्टर विश्लेषण|गुच्छ विश्लेषण]] में ऐसे क्षेत्र उपयोगी होते हैं, जहां समान डेटा बिंदुओं के समूहों को एक साथ वर्गीकृत किया जाता है।
-[[सांख्यिकीय विश्लेषण]] में एक क्षेत्र के भीतर डेटा बिंदुओं के प्रकीर्णन (आँकड़े) को [[माप त्रुटि]] या प्राकृतिक (सामान्यतः ऊष्मा ) प्रक्रियाओं के लिए उत्तरदायी ठहराया जा सकता है, इस स्थिति में गुच्छ एक आदर्श बिंदु के क्षोभ का प्रतिनिधित्व करता है। कुछ परिस्थितियों में इस आदर्श बिंदु का उपयोग गुच्छ में बिंदुओं के विकल्प के रूप में किया जा सकता है, जो गणना समय को कम करने में लाभप्रद है।
+[[सांख्यिकीय विश्लेषण]] में क्षेत्र के भीतर डेटा बिंदुओं के प्रकीर्णन (आँकड़े) को [[माप त्रुटि]] या प्राकृतिक (सामान्यतः ऊष्मा ) प्रक्रियाओं के लिए उत्तरदायी ठहराया जा सकता है, इस स्थिति में गुच्छ एक आदर्श बिंदु के क्षोभ का प्रतिनिधित्व करता है। कुछ परिस्थितियों में इस आदर्श बिंदु का उपयोग गुच्छ में बिंदुओं के विकल्प के रूप में किया जा सकता है, जो गणना समय को कम करने में लाभप्रद है।
 संचालन अनुसंधान में एक उचित समय में [[ एनपी कठिन |एनपी कठोर]] समस्याओं के अनुमानित मानों को प्राप्त करने के लिए निविष्ट की संख्या को कम करने के लिए एक आदर्श बिंदु पर मानों के गुच्छन का भी उपयोग किया जा सकता है। चुना गया बिंदु सामान्यतः क्षेत्र का केंद्र नहीं होता है, क्योंकि यह मुख्य बिंदु से दूर द्वारा अभिनत हो सकता है, परन्तु इसके अतिरिक्त गुच्छ का प्रतिनिधित्व करने के लिए औसत स्थान के कुछ रूप जैसे कम से कम वर्ग बिंदु की गणना की जाती है।
@@ Line 22: / Line 22: @@
 === रैखिक प्रोग्रामन ===
-[[निम्रोद मगिद्दो]] ने 1-केंद्र समस्या का बड़े पैमाने पर अध्ययन किया और 1980 के दशक में कम से कम पांच बार इस पर प्रकाशित किया।<ref>{{cite web |url=http://theory.stanford.edu/~megiddo/bio.html |title = Nimrod Megiddo's resume and publications}}</ref> 1983 में, उन्होंने एक [[छँटाई और खोज]] एल्गोरिदम का प्रस्ताव किया जो इष्टतम सीमक क्षेत्र को खोजता है और रैखिक समय में चलता है यदि आयाम एक स्थिर के रूप में निर्धारित किया गया है। जब आयाम <math>d</math> को ध्यान में रखा जाता है, तो निष्पादन समय जटिलता <math>O(2^{O(d^2)} n)</math> होती है,{{r|meg88}}{{r|chan18}} जो उच्च-आयामी अनुप्रयोगों के लिए अव्यावहारिक है।
+[[निम्रोद मगिद्दो]] ने 1-केंद्र समस्या का बड़े पैमाने पर अध्ययन किया और 1980 के दशक में कम से कम पांच बार इस पर प्रकाशित किया।<ref>{{cite web |url=http://theory.stanford.edu/~megiddo/bio.html |title = Nimrod Megiddo's resume and publications}}</ref> 1983 में, उन्होंने [[छँटाई और खोज]] एल्गोरिदम का प्रस्ताव किया जो इष्टतम सीमक क्षेत्र को खोजता है और रैखिक समय में चलता है यदि आयाम एक स्थिर के रूप में निर्धारित किया गया है। जब आयाम <math>d</math> को ध्यान में रखा जाता है, तो निष्पादन समय जटिलता <math>O(2^{O(d^2)} n)</math> होती है,{{r|meg88}}{{r|chan18}} जो उच्च-आयामी अनुप्रयोगों के लिए अव्यावहारिक है।
-में, [[Emo Welzl|इमो वेलज़ल]] ने [[रायमुंड सीडेल]] द्वारा एक यादृच्छिक [[रैखिक प्रोग्रामिंग|रैखिक प्रोग्रामन]] एल्गोरिदम को सामान्य करते हुए, एक बहुत ही सरल यादृच्छिक एल्गोरिदम का प्रस्ताव दिया। वेलज़ल के एल्गोरिदम का अपेक्षित चलने का समय <math>O((d+1)(d+1)!n)</math> है, जो फिर से किसी निश्चित आयाम <math>d</math> के लिए <math>O(n)</math> में कम हो जाता है। लेख्य उच्च आयामों में इसकी व्यावहारिकता को प्रदर्शित करते हुए प्रायोगिक परिणाम प्रदान करता है।{{r|welzl92}} [[टिमोथी चान]] का एक और वर्तमान नियतात्मक एल्गोरिदम भी आयाम पर कम (परन्तु अभी भी घातीय) निर्भरता के साथ, <math>O(n)</math> समय में चलता है।{{r|chan18}}
+में, [[Emo Welzl|इमो वेलज़ल]] ने [[रायमुंड सीडेल]] द्वारा एक यादृच्छिक [[रैखिक प्रोग्रामिंग|रैखिक प्रोग्रामन]] एल्गोरिदम को सामान्य करते हुए, एक बहुत ही सरल यादृच्छिक एल्गोरिदम का प्रस्ताव दिया। वेलज़ल के एल्गोरिदम का अपेक्षित चलने का समय <math>O((d+1)(d+1)!n)</math> है, जो फिर से किसी निश्चित आयाम <math>d</math> के लिए <math>O(n)</math> में कम हो जाते है। लेख्य उच्च आयामों में इसकी व्यावहारिकता को प्रदर्शित करते हुए प्रायोगिक परिणाम प्रदान करते है।{{r|welzl92}} [[टिमोथी चान]] का एक और वर्तमान नियतात्मक एल्गोरिदम भी आयाम पर कम (परन्तु अभी भी घातीय) निर्भरता के साथ, <math>O(n)</math> समय में चलते है।{{r|chan18}}
 ओपन-सोर्स [[कम्प्यूटेशनल ज्यामिति एल्गोरिदम लाइब्रेरी]] (सीजीएएल) में वेल्ज़ल के एल्गोरिदम का कार्यान्वयन सम्मिलित है।<ref>[http://doc.cgal.org/latest/Bounding_volumes/classCGAL_1_1Min__sphere__of__spheres__d.html CGAL 4.3 - Bounding Volumes - Min_sphere_of_spheres_d], retrieved 2014-03-30.</ref>
@@ Line 30: / Line 30: @@
 === रिटर का सीमक क्षेत्र ===
-में, जैक रिटर ने गैर-न्यूनतम सीमक क्षेत्र खोजने के लिए एक सरल एल्गोरिदम प्रस्तावित किया।{{r|Ritter1990}} इसकी सादगी के लिए इसका व्यापक रूप से विभिन्न अनुप्रयोगों में उपयोग किया जाता है। एल्गोरिदम इस प्रकार काम करता है:
+में, जैक रिटर ने गैर-न्यूनतम सीमक क्षेत्र खोजने के लिए सरल एल्गोरिदम प्रस्तावित किया।{{r|Ritter1990}} इसकी सादगी के लिए इसका व्यापक रूप से विभिन्न अनुप्रयोगों में उपयोग किया जाता है। एल्गोरिदम इस प्रकार काम करता है:
 # <math>P</math> से एक बिंदु <math>x</math> चुनें, <math>P</math> में एक बिंदु <math>y</math> खोजें, जिसकी <math>x</math> से सबसे बड़ी दूरी हो;
 # <math>P</math> में एक बिंदु <math>z</math> खोजें, जिसकी <math>y</math> से सबसे बड़ी दूरी हो। <math>y</math> और <math>z</math> के मध्य बिंदु के रूप में इसके केंद्र के साथ एक प्रारंभिक गेंद <math>B</math> समूहित करें , <math>y</math> और <math>z</math> के बीच की दूरी के आधे के रूप में त्रिज्या;
-#यदि <math>P</math> में सभी बिंदु गेंद <math>B</math> के भीतर हैं , तब हमें एक परिबद्ध गोला मिलता है। अन्यथा, <math>p</math> को गेंद के बाहर एक बिंदु होने दें, बिंदु <math>p</math> और पिछली गेंद दोनों को आच्छादन करते हुए एक नवीन गेंद का निर्माण करें। इस चरण को तब तक दोहराएं जब तक कि सभी बिंदु आच्छादित न हो जाएं।
+#यदि <math>P</math> में सभी बिंदु गेंद <math>B</math> के भीतर हैं , तब हमें एक परिबद्ध गोला मिलता है। अन्यथा, <math>p</math> को गेंद के बाहर एक बिंदु होने दें, बिंदु <math>p</math> और पिछली गेंद दोनों को आच्छादन करते हुए नवीन गेंद का निर्माण करें। इस चरण को तब तक दोहराएं जब तक कि सभी बिंदु आच्छादित न हो जाएं।
-रिटर का एल्गोरिदम <math>d</math>-आयामी स्थान में <math>n</math> बिन्दु वाले निविष्ट पर समय <math>O(nd)</math> में चलता है, जो इसे बहुत कुशल बनाता है। यद्यपि यह मात्र स्थूल परिणाम देता है जो सामान्यतः इष्टतम से 5% से 20% बड़ा होता है।{{citation needed|date=November 2015}}
+रिटर का एल्गोरिदम <math>d</math>-आयामी स्थान में <math>n</math> बिन्दु वाले निविष्ट पर समय <math>O(nd)</math> में चलता है, जो इसे बहुत कुशल बनाते है। यद्यपि यह मात्र स्थूल परिणाम देते है जो सामान्यतः इष्टतम से 5% से 20% बड़ा होता है।{{citation needed|date=November 2015}}
 === क्रोड-समुच्चय आधारित सन्निकटन ===
@@ Line 46: / Line 46: @@
 === फिशर का यथार्थ हलकर्ता ===
-फिशर एट अल. (2003) ने एक यथार्थ हलकर्ता प्रस्तावित किया, यद्यपि सबसे निकृष्टतम स्थिति में एल्गोरिदम में बहुपद चलने का समय नहीं है।{{r|Fischer2003}} एल्गोरिदम विशुद्ध रूप से संयोजी है और रैखिक प्रोग्रामन के लिए सरलीकृत विधि के समान एक धुरी योजना को लागू करता है, जिसका उपयोग पहले कुछ अनुमानों में किया गया था। यह एक बड़े गोले से प्रारम्भ होता है जो सभी बिंदुओं को आच्छादित करता है और धीरे-धीरे इसे तब तक सिकोड़ता है जब तक कि इसे और छोटा नहीं किया जा सकता। एल्गोरिदम अध:पतन के स्थितियों में सही समापन नियम प्रस्तुत करता है, जिसे पूर्व लेखकों द्वारा अनदेखा किया जाता है; और आंशिक हलों का कुशल संचालन, जो एक प्रमुख गति-अप पैदा करता है। लेखकों ने सत्यापित किया कि एल्गोरिदम कम और मध्यम रूप से निम्न (10,000 तक) आयामों में व्यवहार में कुशल है और अनुरोध करता है कि यह अपने चल बिन्दु संचालन में संख्यात्मक स्थिरता की समस्याओं को प्रदर्शित नहीं करता है।{{r|Fischer2003}} एल्गोरिदम का एक C++ कार्यान्वयन खुला स्त्रोत प्रोजेक्ट के रूप में उपलब्ध है।<ref> [https://github.com/hbf/miniball miniball open-source project]</ref>
+फिशर एट अल. (2003) ने एक यथार्थ हलकर्ता प्रस्तावित किया, यद्यपि सबसे निकृष्टतम स्थिति में एल्गोरिदम में बहुपद चलने का समय नहीं है।{{r|Fischer2003}} एल्गोरिदम विशुद्ध रूप से संयोजी है और रैखिक प्रोग्रामन के लिए सरलीकृत विधि के समान एक धुरी योजना को लागू करते है, जिसका उपयोग पहले कुछ अनुमानों में किया गया था। यह एक बड़े गोले से प्रारम्भ होता है जो सभी बिंदुओं को आच्छादित करता है और धीरे-धीरे इसे तब तक सिकोड़ता है जब तक कि इसे और छोटा नहीं किया जा सकता है। एल्गोरिदम अध:पतन की स्थितियों में सही समापन नियम प्रस्तुत करती है, जिसे पूर्व लेखकों द्वारा अनदेखा किया जाता है; और आंशिक हलों का कुशल संचालन, जो एक प्रमुख गति-अप उत्पन्न करता है। लेखकों ने सत्यापित किया कि एल्गोरिदम कम और मध्यम रूप से निम्न (10,000 तक) आयामों में व्यवहार में कुशल है और अनुरोध करते है कि यह अपने चल बिन्दु संचालन में संख्यात्मक स्थिरता की समस्याओं को प्रदर्शित नहीं करते है।{{r|Fischer2003}} एल्गोरिदम का एक C++ कार्यान्वयन खुला स्त्रोत प्रोजेक्ट के रूप में उपलब्ध है।<ref> [https://github.com/hbf/miniball miniball open-source project]</ref>
 === परम बिंदु इष्टतम क्षेत्र ===
-{{harvtxt|लार्सन|2008}} सीमक स्फीयर समस्या को हल करने के लिए नियंत्रणीय गति से यथार्थता सन्निकटन के साथ "परम बिंदु इष्टतम क्षेत्र" विधि प्रस्तावित की। यह विधि <math>s</math> दिशा सदिश का एक समुच्चय लेकर काम करती है और <math>s</math> प्रत्येक सदिश पर सभी बिंदुओं को प्रक्षेपित करती है; गति-यथार्थता व्यापार-बंद चर के रूप में कार्य करता है। इन अनुमानों के <math>2s</math> परम बिंदुओं पर एक यथार्थ हलकर्ता लगाया जाता है। एल्गोरिदम तब शेष बिंदुओं पर पुनरावृति करता है, यदि कोई हो, यदि आवश्यक हो तो गोले को बढ़ाना। बड़े <math>n</math> के लिए यह विधि तुलनीय परिणाम देते हुए यथार्थ विधियों की तुलना में तीव्रता से परिमाण का क्रम है। इसमें <math>O(sn)</math> का सबसे निकृष्टतम समय है।{{r|epos}}
+{{harvtxt|लार्सन|2008}} सीमक स्फीयर समस्या को हल करने के लिए नियंत्रणीय गति से यथार्थता सन्निकटन के साथ "परम बिंदु इष्टतम क्षेत्र" विधि प्रस्तावित की। यह विधि <math>s</math> दिशा सदिश का समुच्चय लेकर काम करती है और <math>s</math> प्रत्येक सदिश पर सभी बिंदुओं को प्रक्षेपित करती है; गति-यथार्थता व्यापार-बंद चर के रूप में कार्य करते है। इन अनुमानों के <math>2s</math> परम बिंदुओं पर एक यथार्थ हलकर्ता लगाए जाते है। एल्गोरिदम तब शेष बिंदुओं पर पुनरावृति करता है, यदि कोई हो, यदि आवश्यक हो तो गोले को बढ़ाना। बड़े <math>n</math> के लिए यह विधि तुलनीय परिणाम देते हुए यथार्थ विधियों की तुलना में तीव्रता से परिमाण का क्रम है। इसमें <math>O(sn)</math> का सबसे निकृष्टतम समय है।{{r|epos}}
 == यह भी देखें ==

Anonymous

Search

सीमा क्षेत्र: Difference between revisions

Namespaces

More

Page actions