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

Revision as of 08:53, 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] इसकी सादगी के लिए इसका व्यापक रूप से विभिन्न अनुप्रयोगों में उपयोग किया जाता है। एल्गोरिदम इस प्रकार काम करता है:

एक बिंदु चुनें $x$ से $P$ , एक बिंदु खोजें $y$ में $P$ , जिसकी स�

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
 {{Short description|Sphere that contains a set of objects}}
-{{for|the planar problem|Bounding circle}}
+{{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-केंद्र समस्या]] के रूप में भी जाना जाता है।
+न्यूनतम सीमक गोले के केंद्र की गणना करने की समस्या को भारित यूक्लिडियन [[1-केंद्र समस्या]] के रूप में भी जाना जाता है।
 == अनुप्रयोग ==
-=== क्लस्टरिंग ===
+=== गुच्छन ===
-[[क्लस्टर विश्लेषण]] में ऐसे क्षेत्र उपयोगी होते हैं, जहां समान डेटा बिंदुओं के समूहों को एक साथ वर्गीकृत किया जाता है।
+[[क्लस्टर विश्लेषण|गुच्छ विश्लेषण]] में ऐसे क्षेत्र उपयोगी होते हैं, जहां समान डेटा बिंदुओं के समूहों को एक साथ वर्गीकृत किया जाता है।
-[[सांख्यिकीय विश्लेषण]] में एक क्षेत्र के भीतर डेटा बिंदुओं के प्रकीर्णन (आँकड़े) को [[माप त्रुटि]] या प्राकृतिक (आमतौर पर थर्मल) प्रक्रियाओं के लिए जिम्मेदार ठहराया जा सकता है, इस मामले में क्लस्टर एक आदर्श बिंदु के गड़बड़ी का प्रतिनिधित्व करता है। कुछ परिस्थितियों में इस आदर्श बिंदु का उपयोग क्लस्टर में बिंदुओं के विकल्प के रूप में किया जा सकता है, जो गणना समय को कम करने में लाभप्रद है।
+[[सांख्यिकीय विश्लेषण]] में एक क्षेत्र के भीतर डेटा बिंदुओं के प्रकीर्णन (आँकड़े) को [[माप त्रुटि]] या प्राकृतिक (सामान्यतः ऊष्मा ) प्रक्रियाओं के लिए उत्तरदायी ठहराया जा सकता है, इस स्थिति में गुच्छ एक आदर्श बिंदु के क्षोभ का प्रतिनिधित्व करता है। कुछ परिस्थितियों में इस आदर्श बिंदु का उपयोग गुच्छ में बिंदुओं के विकल्प के रूप में किया जा सकता है, जो गणना समय को कम करने में लाभप्रद है।
-संचालन अनुसंधान में एक उचित समय में [[ एनपी कठिन ]] समस्याओं के अनुमानित मूल्यों को प्राप्त करने के लिए इनपुट की संख्या को कम करने के लिए एक आदर्श बिंदु पर मूल्यों के क्लस्टरिंग का भी उपयोग किया जा सकता है। चुना गया बिंदु आमतौर पर क्षेत्र का केंद्र नहीं होता है, क्योंकि यह आउटलेयर द्वारा पक्षपाती हो सकता है, लेकिन इसके बजाय क्लस्टर का प्रतिनिधित्व करने के लिए औसत स्थान के कुछ रूप जैसे कम से कम वर्ग बिंदु की गणना की जाती है।
+संचालन अनुसंधान में एक उचित समय में [[ एनपी कठिन |एनपी कठोर]] समस्याओं के अनुमानित मानों को प्राप्त करने के लिए निविष्ट की संख्या को कम करने के लिए एक आदर्श बिंदु पर मानों के गुच्छन का भी उपयोग किया जा सकता है। चुना गया बिंदु सामान्यतः क्षेत्र का केंद्र नहीं होता है, क्योंकि यह मुख्य बिंदु से दूर द्वारा अभिनत हो सकता है, परन्तु इसके अतिरिक्त गुच्छ का प्रतिनिधित्व करने के लिए औसत स्थान के कुछ रूप जैसे कम से कम वर्ग बिंदु की गणना की जाती है।
 == एल्गोरिदम ==
-बाउंडिंग स्फेयर समस्या को हल करने के लिए सटीक और अनुमानित एल्गोरिदम हैं।
+सीमक क्षेत्र समस्या को हल करने के लिए यथार्थ और अनुमानित एल्गोरिदम हैं।
-=== लीनियर प्रोग्रामिंग ===
+=== लीनियर प्रोग्रामन ===
-[[निम्रोद मगिद्दो]] ने 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]] ने [[रायमुंड सीडेल]] द्वारा एक यादृच्छिक [[रैखिक प्रोग्रामिंग]] एल्गोरिथ्म को सामान्य करते हुए, एक बहुत ही सरल यादृच्छिक एल्गोरिथ्म का प्रस्ताव दिया। Welzl के एल्गोरिथम का अपेक्षित रनिंग टाइम है <math>O((d+1)(d+1)!n)</math>, जो फिर से कम हो जाता है <math>O(n)</math> किसी निश्चित आयाम के लिए <math>d</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>
+ओपन-सोर्स [[कम्प्यूटेशनल ज्यामिति एल्गोरिदम लाइब्रेरी]] (सीजीएएल) में वेल्ज़ल के एल्गोरिदम का कार्यान्वयन सम्मिलित है।<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>
-=== रिटर का बाउंडिंग स्फेयर ===
+=== रिटर का सीमक क्षेत्र ===
-में, जैक रिटर ने गैर-न्यूनतम बाउंडिंग क्षेत्र खोजने के लिए एक सरल एल्गोरिथम प्रस्तावित किया।{{r|Ritter1990}} इसकी सादगी के लिए इसका व्यापक रूप से विभिन्न अनुप्रयोगों में उपयोग किया जाता है। एल्गोरिथ्म इस तरह काम करता है:
+में, जैक रिटर ने गैर-न्यूनतम सीमक क्षेत्र खोजने के लिए एक सरल एल्गोरिदम प्रस्तावित किया।{{r|Ritter1990}} इसकी सादगी के लिए इसका व्यापक रूप से विभिन्न अनुप्रयोगों में उपयोग किया जाता है। एल्गोरिदम इस प्रकार काम करता है:
 # एक बिंदु चुनें <math>x</math> से <math>P</math>, एक बिंदु खोजें <math>y</math> में <math>P</math>, जिसकी सबसे बड़ी दूरी है <math>x</math>;
-# एक बिंदु खोजें <math>z</math> में <math>P</math>, जिसकी सबसे बड़ी दूरी है <math>y</math>. एक प्रारंभिक गेंद सेट करें <math>B</math>, के मध्य बिंदु के रूप में इसके केंद्र के साथ <math>y</math> और <math>z</math>, त्रिज्या बीच की दूरी के आधे के रूप में <math>y</math> और <math>z</math>;
+# एक बिंदु खोजें <math>z</math> में <math>P</math>, जिसकी सबसे बड़ी दूरी है <math>y</math>। एक प्रारंभिक गेंद समुच्चय करें <math>B</math>, के मध्य बिंदु के रूप में इसके केंद्र के साथ <math>y</math> और <math>z</math>, त्रिज्या बीच की दूरी के आधे के रूप में <math>y</math> और <math>z</math>;
 #यदि सभी बिंदु अंदर हैं <math>P</math> गेंद के भीतर हैं <math>B</math>, तब हमें एक परिबद्ध गोला मिलता है। नहीं तो जाने दो <math>p</math> गेंद के बाहर एक बिंदु बनें, दोनों बिंदुओं को कवर करते हुए एक नई गेंद का निर्माण करें <math>p</math> और पिछली गेंद। इस चरण को तब तक दोहराएं जब तक कि सभी बिंदु कवर न हो जाएं।
-रिटर का एल्गोरिदम समय में चलता है <math>O(nd)</math> से मिलकर इनपुट पर <math>n</math> में इंगित करता है <math>d</math>-आयामी स्थान, जो इसे बहुत कुशल बनाता है। हालांकि यह केवल मोटे परिणाम देता है जो आमतौर पर इष्टतम से 5% से 20% बड़ा होता है।{{citation needed|date=November 2015}}
+रिटर का एल्गोरिदम समय में चलता है <math>O(nd)</math> से मिलकर निविष्ट पर <math>n</math> में इंगित करता है <math>d</math>-आयामी स्थान, जो इसे बहुत कुशल बनाता है। हालांकि यह केवल मोटे परिणाम देता है जो सामान्यतः इष्टतम से 5% से 20% बड़ा होता है।{{citation needed|date=November 2015}}
-=== कोर-सेट आधारित सन्निकटन ===
+=== कोर-समुच्चय आधारित सन्निकटन ===
-बदोइउ एट अल। एक प्रस्तुत किया <math>1+\varepsilon</math> सीमा क्षेत्र समस्या के सन्निकटन,{{r|Badoiu2002}} जहाँ एक <math>1+\varepsilon</math> सन्निकटन का अर्थ है कि निर्मित क्षेत्र में अधिकतम त्रिज्या है <math>(1+\varepsilon)r</math>, कहाँ <math>r</math> एक बाउंडिंग गोले की सबसे छोटी संभव त्रिज्या है।
+बदोइउ एट अल। एक प्रस्तुत किया <math>1+\varepsilon</math> सीमा क्षेत्र समस्या के सन्निकटन,{{r|Badoiu2002}} जहाँ एक <math>1+\varepsilon</math> सन्निकटन का अर्थ है कि निर्मित क्षेत्र में अधिकतम त्रिज्या है <math>(1+\varepsilon)r</math>, कहाँ <math>r</math> एक सीमक गोले की सबसे छोटी संभव त्रिज्या है।
-[[ कोर सेट ]] एक छोटा उपसमुच्चय होता है, जो कि a <math>1+\varepsilon</math> उपसमुच्चय पर विलयन का विस्तार पूरे समुच्चय का परिबद्ध क्षेत्र है। प्रत्येक पुनरावृत्ति में सेट में सबसे दूर के बिंदु को जोड़कर कोरसेट का निर्माण वृद्धिशील रूप से किया जाता है।
+[[ कोर सेट | कोर समुच्चय]] एक छोटा उपसमुच्चय होता है, जो कि a <math>1+\varepsilon</math> उपसमुच्चय पर विलयन का विस्तार पूरे समुच्चय का परिबद्ध क्षेत्र है। प्रत्येक पुनरावृत्ति में समुच्चय में सबसे दूर के बिंदु को जोड़कर कोरसमुच्चय का निर्माण वृद्धिशील रूप से किया जाता है।
-कुमार एट अल। इस सन्निकटन एल्गोरिथ्म में सुधार किया{{r|kumar2003}} ताकि यह समय पर चले <math>O(\frac{nd}{\epsilon}+ \frac{1}{\epsilon^{4.5}}\log{\frac{1}{\epsilon}})</math>.
+कुमार एट अल। इस सन्निकटन एल्गोरिदम में सुधार किया{{r|kumar2003}} ताकि यह समय पर चले <math>O(\frac{nd}{\epsilon}+ \frac{1}{\epsilon^{4.5}}\log{\frac{1}{\epsilon}})</math>।
-=== फिशर का सटीक सॉल्वर ===
+=== फिशर का यथार्थ सॉल्वर ===
-फिशर एट अल। (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|Larsson|2008}} बाउंडिंग स्फीयर समस्या को हल करने के लिए सटीकता सन्निकटन के लिए नियंत्रणीय गति के साथ एक्सट्रीमल पॉइंट्स ऑप्टीमल स्फेयर विधि प्रस्तावित की। यह विधि का एक सेट लेकर काम करती है <math>s</math> दिशा वैक्टर और प्रत्येक वेक्टर पर सभी बिंदुओं को प्रोजेक्ट करना <math>s</math>; <math>s</math> गति-सटीकता व्यापार-बंद चर के रूप में कार्य करता है। एक सटीक सॉल्वर पर लागू होता है <math>2s</math> इन अनुमानों के चरम बिंदु। एल्गोरिथ्म तब शेष बिंदुओं पर पुनरावृति करता है, यदि कोई हो, यदि आवश्यक हो तो गोले को बढ़ाना। बड़े के लिए <math>n</math> तुलनात्मक परिणाम देते हुए, यह विधि सटीक विधियों की तुलना में परिमाण के क्रम में तेजी से है। इसका सबसे खराब समय है <math>O(sn)</math>. {{r|epos}}
+{{harvtxt|Larsson|2008}} सीमक स्फीयर समस्या को हल करने के लिए यथार्थता सन्निकटन के लिए नियंत्रणीय गति के साथ एक्सट्रीमल पॉइंट्स ऑप्टीमल क्षेत्र विधि प्रस्तावित की। यह विधि का एक समुच्चय लेकर काम करती है <math>s</math> दिशा वैक्टर और प्रत्येक वेक्टर पर सभी बिंदुओं को प्रोजेक्ट करना <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