सीमा क्षेत्र: Difference between revisions
No edit summary |
No edit summary |
||
| Line 32: | Line 32: | ||
1990 में, जैक रिटर ने गैर-न्यूनतम सीमक क्षेत्र खोजने के लिए एक सरल एल्गोरिदम प्रस्तावित किया।{{r|Ritter1990}} इसकी सादगी के लिए इसका व्यापक रूप से विभिन्न अनुप्रयोगों में उपयोग किया जाता है। एल्गोरिदम इस प्रकार काम करता है: | 1990 में, जैक रिटर ने गैर-न्यूनतम सीमक क्षेत्र खोजने के लिए एक सरल एल्गोरिदम प्रस्तावित किया।{{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>d</math>-आयामी स्थान में <math>n</math> बिन्दु वाले निविष्ट पर समय <math>O(nd)</math> में चलता है, जो इसे बहुत कुशल बनाता है। यद्यपि यह मात्र स्थूल परिणाम देता है जो सामान्यतः इष्टतम से 5% से 20% बड़ा होता है।{{citation needed|date=November 2015}} | ||
=== | === क्रोड-समुच्चय आधारित सन्निकटन === | ||
बदोइउ एट | बदोइउ एट अल. ने सीमा क्षेत्र समस्या के <math>1+\varepsilon</math> सन्निकटन सन्निकटन प्रस्तुत किया, जहाँ <math>1+\varepsilon</math> सन्निकटन का अर्थ है कि निर्मित गोले में अधिकतम <math>(1+\varepsilon)r</math>, पर त्रिज्या है, जहाँ <math>r</math> एक सीमा क्षेत्र का सबसे छोटा संभव त्रिज्या है। | ||
[[ कोर सेट | | [[ कोर सेट |क्रोड समुच्चय]] एक छोटा उपसमुच्चय है, कि उपसमुच्चय पर विलयन <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) ने एक यथार्थ सॉल्वर प्रस्तावित किया, | फिशर एट अल। (2003) ने एक यथार्थ सॉल्वर प्रस्तावित किया, यद्यपि सबसे खराब स्थिति में एल्गोरिदम में बहुपद चलने का समय नहीं है।{{r|Fischer2003}} एल्गोरिदम विशुद्ध रूप से संयोजी है और रैखिक प्रोग्रामन के लिए सिम्पलेक्स विधि के समान एक धुरी योजना को लागू करता है, जिसका उपयोग पहले कुछ अनुमानों में किया गया था। यह एक बड़े गोले से शुरू होता है जो सभी बिंदुओं को आच्छादित करता है और धीरे-धीरे इसे तब तक सिकोड़ता है जब तक कि इसे और छोटा नहीं किया जा सकता। एल्गोरिदम अध:पतन के स्थितियों में सही समापन नियम प्रस्तुत करता है, जिसे पूर्व लेखकों द्वारा अनदेखा किया जाता है; और आंशिक समाधानों का कुशल संचालन, जो एक प्रमुख गति-अप पैदा करता है। लेखकों ने सत्यापित किया कि एल्गोरिदम कम और मध्यम रूप से निम्न (10,000 तक) आयामों में व्यवहार में कुशल है और दावा करता है कि यह अपने फ़्लोटिंग-पॉइंट संचालन में संख्यात्मक स्थिरता की समस्याओं को प्रदर्शित नहीं करता है।{{r|Fischer2003}} एल्गोरिदम का एक C++ कार्यान्वयन ओपन-सोर्स प्रोजेक्ट के रूप में उपलब्ध है।<ref> [https://github.com/hbf/miniball miniball open-source project]</ref> | ||
Revision as of 10:09, 27 April 2023
गणित में, आयामी स्थान परिमित विस्तार की वस्तुओं का एक गैर-रिक्त समुच्चय दिया गया है , उदाहरण के लिए बिंदुओं का एक समुच्चय, एक सीमक क्षेत्र, परिबद्ध क्षेत्र या परिबद्ध गेंद उस समुच्चय के लिए आयामी ठोस गोला है जिसमें ये सभी वस्तुएं होती हैं।
कंप्यूटर चित्रलेख और कम्प्यूटेशनल ज्यामिति में प्रयुक्त, एक सीमक क्षेत्र एक विशेष प्रकार की सीमक मात्रा है। वास्तविक समय के कंप्यूटर चित्रलेख अनुप्रयोगों में उच्च व्यावहारिक मान के साथ कई तीव्र और सरल सीमक क्षेत्र निर्माण एल्गोरिदम हैं।[1]
सांख्यिकी और संचालन अनुसंधान में, वस्तुएं सामान्यतः बिंदु होती हैं, और सामान्यतः ब्याज का क्षेत्र न्यूनतम सीमा क्षेत्र होता है, अर्थात, सभी सीमा क्षेत्रों के बीच न्यूनतम त्रिज्या वाला क्षेत्र। यह सिद्ध किया जा सकता है कि ऐसा क्षेत्र अद्वितीय है: यदि उनमें से दो हैं, तो विचाराधीन वस्तुएँ उनके प्रतिच्छेदन के भीतर स्थित हैं। परन्तु समान त्रिज्या वाले दो असंपाती गोलों का प्रतिच्छेदन छोटे त्रिज्या वाले गोले में निहित होता है।
न्यूनतम सीमक गोले के केंद्र की गणना करने की समस्या को भारित यूक्लिडियन 1-केंद्र समस्या के रूप में भी जाना जाता है।
अनुप्रयोग
गुच्छन
गुच्छ विश्लेषण में ऐसे क्षेत्र उपयोगी होते हैं, जहां समान डेटा बिंदुओं के समूहों को एक साथ वर्गीकृत किया जाता है।
सांख्यिकीय विश्लेषण में एक क्षेत्र के भीतर डेटा बिंदुओं के प्रकीर्णन (आँकड़े) को माप त्रुटि या प्राकृतिक (सामान्यतः ऊष्मा ) प्रक्रियाओं के लिए उत्तरदायी ठहराया जा सकता है, इस स्थिति में गुच्छ एक आदर्श बिंदु के क्षोभ का प्रतिनिधित्व करता है। कुछ परिस्थितियों में इस आदर्श बिंदु का उपयोग गुच्छ में बिंदुओं के विकल्प के रूप में किया जा सकता है, जो गणना समय को कम करने में लाभप्रद है।
संचालन अनुसंधान में एक उचित समय में एनपी कठोर समस्याओं के अनुमानित मानों को प्राप्त करने के लिए निविष्ट की संख्या को कम करने के लिए एक आदर्श बिंदु पर मानों के गुच्छन का भी उपयोग किया जा सकता है। चुना गया बिंदु सामान्यतः क्षेत्र का केंद्र नहीं होता है, क्योंकि यह मुख्य बिंदु से दूर द्वारा अभिनत हो सकता है, परन्तु इसके अतिरिक्त गुच्छ का प्रतिनिधित्व करने के लिए औसत स्थान के कुछ रूप जैसे कम से कम वर्ग बिंदु की गणना की जाती है।
एल्गोरिदम
सीमक क्षेत्र समस्या को हल करने के लिए यथार्थ और अनुमानित एल्गोरिदम हैं।
लीनियर प्रोग्रामन
निम्रोद मगिद्दो ने 1-केंद्र समस्या का बड़े पैमाने पर अध्ययन किया और 1980 के दशक में कम से कम पांच बार इस पर प्रकाशित किया।[2] 1983 में, उन्होंने एक छँटाई और खोज एल्गोरिदम का प्रस्ताव किया जो इष्टतम सीमक क्षेत्र को खोजता है और रैखिक समय में चलता है यदि आयाम एक स्थिर के रूप में निर्धारित किया गया है। जब आयाम को ध्यान में रखा जाता है, तो निष्पादन समय जटिलता होती है,[3][4] जो उच्च-आयामी अनुप्रयोगों के लिए अव्यावहारिक है।
1991 में, इमो वेलज़ल ने रायमुंड सीडेल द्वारा एक यादृच्छिक रैखिक प्रोग्रामन एल्गोरिदम को सामान्य करते हुए, एक बहुत ही सरल यादृच्छिक एल्गोरिदम का प्रस्ताव दिया। वेलज़ल के एल्गोरिदम का अपेक्षित चलने का समय है, जो फिर से किसी निश्चित आयाम के लिए में कम हो जाता है। लेख्य उच्च आयामों में इसकी व्यावहारिकता को प्रदर्शित करते हुए प्रायोगिक परिणाम प्रदान करता है।[5] टिमोथी चान का एक और वर्तमान नियतात्मक एल्गोरिदम भी आयाम पर कम (परन्तु अभी भी घातीय) निर्भरता के साथ, समय में चलता है।[4]
ओपन-सोर्स कम्प्यूटेशनल ज्यामिति एल्गोरिदम लाइब्रेरी (सीजीएएल) में वेल्ज़ल के एल्गोरिदम का कार्यान्वयन सम्मिलित है।[6]
रिटर का सीमक क्षेत्र
1990 में, जैक रिटर ने गैर-न्यूनतम सीमक क्षेत्र खोजने के लिए एक सरल एल्गोरिदम प्रस्तावित किया।[7] इसकी सादगी के लिए इसका व्यापक रूप से विभिन्न अनुप्रयोगों में उपयोग किया जाता है। एल्गोरिदम इस प्रकार काम करता है:
- से एक बिंदु चुनें, में एक बिंदु खोजें, जिसकी से सबसे बड़ी दूरी हो;
- में एक बिंदु खोजें, जिसकी से सबसे बड़ी दूरी हो। और के मध्य बिंदु के रूप में इसके केंद्र के साथ एक प्रारंभिक गेंद समूहित करें , और के बीच की दूरी के आधे के रूप में त्रिज्या;
- यदि में सभी बिंदु गेंद के भीतर हैं , तब हमें एक परिबद्ध गोला मिलता है। अन्यथा, को गेंद के बाहर एक बिंदु होने दें, बिंदु और पिछली गेंद दोनों को आच्छादन करते हुए एक नवीन गेंद का निर्माण करें। इस चरण को तब तक दोहराएं जब तक कि सभी बिंदु आच्छादित न हो जाएं।
रिटर का एल्गोरिदम -आयामी स्थान में बिन्दु वाले निविष्ट पर समय में चलता है, जो इसे बहुत कुशल बनाता है। यद्यपि यह मात्र स्थूल परिणाम देता है जो सामान्यतः इष्टतम से 5% से 20% बड़ा होता है।[citation needed]
क्रोड-समुच्चय आधारित सन्निकटन
बदोइउ एट अल. ने सीमा क्षेत्र समस्या के सन्निकटन सन्निकटन प्रस्तुत किया, जहाँ सन्निकटन का अर्थ है कि निर्मित गोले में अधिकतम , पर त्रिज्या है, जहाँ एक सीमा क्षेत्र का सबसे छोटा संभव त्रिज्या है।
क्रोड समुच्चय एक छोटा उपसमुच्चय है, कि उपसमुच्चय पर विलयन पूरे समुच्चय का परिबद्ध क्षेत्र है। प्रत्येक पुनरावृत्ति में समुच्चय में सबसे दूर के बिंदु को जोड़कर क्रोडसमुच्चय का निर्माण वृद्धिशील रूप से किया जाता है।
कुमार एट अल। इस सन्निकटन एल्गोरिदम में सुधार किया[8] ताकि यह समय पर चले ।
फिशर का यथार्थ सॉल्वर
फिशर एट अल। (2003) ने एक यथार्थ सॉल्वर प्रस्तावित किया, यद्यपि सबसे खराब स्थिति में एल्गोरिदम में बहुपद चलने का समय नहीं है।[9] एल्गोरिदम विशुद्ध रूप से संयोजी है और रैखिक प्रोग्रामन के लिए सिम्पलेक्स विधि के समान एक धुरी योजना को लागू करता है, जिसका उपयोग पहले कुछ अनुमानों में किया गया था। यह एक बड़े गोले से शुरू होता है जो सभी बिंदुओं को आच्छादित करता है और धीरे-धीरे इसे तब तक सिकोड़ता है जब तक कि इसे और छोटा नहीं किया जा सकता। एल्गोरिदम अध:पतन के स्थितियों में सही समापन नियम प्रस्तुत करता है, जिसे पूर्व लेखकों द्वारा अनदेखा किया जाता है; और आंशिक समाधानों का कुशल संचालन, जो एक प्रमुख गति-अप पैदा करता है। लेखकों ने सत्यापित किया कि एल्गोरिदम कम और मध्यम रूप से निम्न (10,000 तक) आयामों में व्यवहार में कुशल है और दावा करता है कि यह अपने फ़्लोटिंग-पॉइंट संचालन में संख्यात्मक स्थिरता की समस्याओं को प्रदर्शित नहीं करता है।[9] एल्गोरिदम का एक C++ कार्यान्वयन ओपन-सोर्स प्रोजेक्ट के रूप में उपलब्ध है।[10]
चरम बिंदु इष्टतम क्षेत्र
Larsson (2008) सीमक स्फीयर समस्या को हल करने के लिए यथार्थता सन्निकटन के लिए नियंत्रणीय गति के साथ एक्सट्रीमल पॉइंट्स ऑप्टीमल क्षेत्र विधि प्रस्तावित की। यह विधि का एक समुच्चय लेकर काम करती है दिशा वैक्टर और प्रत्येक वेक्टर पर सभी बिंदुओं को प्रोजेक्ट करना ; गति-यथार्थता व्यापार-बंद चर के रूप में कार्य करता है। एक यथार्थ सॉल्वर पर लागू होता है इन अनुमानों के चरम बिंदु। एल्गोरिदम तब शेष बिंदुओं पर पुनरावृति करता है, यदि कोई हो, यदि आवश्यक हो तो गोले को बढ़ाना। बड़े के लिए तुलनात्मक परिणाम देते हुए, यह विधि यथार्थ विधियों की तुलना में परिमाण के क्रम में तीव्री से है। इसका सबसे खराब समय है । [1]
यह भी देखें
- सीमक मात्रा
- परिबद्ध गोला, परिबद्ध वृत्त
संदर्भ
- ↑ 1.0 1.1 Larsson, Thomas (2008), "Fast and tight fitting bounding spheres", SIGRAD 2008: The Annual SIGRAD Conference, Special Theme: Interaction, November 27-28, 2008, Stockholm, Sweden, Linköping Electronic Conference Proceedings, vol. 34, Linköping, Sweden: Linköping University
- ↑ "Nimrod Megiddo's resume and publications".
- ↑ Megiddo, Nimrod (1988). "Linear programming in linear time when the dimension is fixed". Journal of the ACM. 33 (1): 114–147. doi:10.1145/2422.322418.
- ↑ 4.0 4.1 Chan, Timothy (2018). "Improved deterministic algorithms for linear programming in low dimensions". ACM Transactions on Algorithms. 14 (3): Article 30, 10 pages. doi:10.1145/3155312.
- ↑ Welzl, Emo (1991), "Smallest enclosing disks (balls and ellipsoids)", in Maurer, Hermann (ed.), New Results and New Trends in Computer Science: Graz, Austria, June 20–21, 1991, Proceedings, Lecture Notes in Computer Science, vol. 555, Berlin, Germany: Springer, pp. 359–370, doi:10.1007/BFb0038202, MR 1254721
- ↑ CGAL 4.3 - Bounding Volumes - Min_sphere_of_spheres_d, retrieved 2014-03-30.
- ↑ Ritter, Jack (1990), "An efficient bounding sphere", in Glassner, Andrew S. (ed.), Graphics Gems, San Diego, CA, US: Academic Press Professional, Inc., pp. 301–303, ISBN 0-12-286166-3
- ↑ Kumar, Piyush; Mitchell, Joseph S. B.; Yıldırım, E. Alper (2003), "Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions", in Ladner, Richard E. (ed.), Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, Baltimore, MD, USA, January 11, 2003, Philadelphia, PA, US: SIAM, pp. 45–55
- ↑ 9.0 9.1 Fischer, Kaspar; Gärtner, Bernd; Kutz, Martin (2003), "Fast smallest-enclosing-ball computation in high dimensions" (PDF), in Battista, Giuseppe Di; Zwick, Uri (eds.), Algorithms: ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings (PDF), Lecture Notes in Computer Science, vol. 2832, Springer, Berlin, pp. 630–641, doi:10.1007/978-3-540-39658-1_57
- ↑ miniball open-source project
<ref> tag with name "Badoiu2002" defined in <references> is not used in prior text.
बाहरी संबंध
- Smallest Enclosing Circle Problem – describes several algorithms for enclosing a point set, including Megiddo's linear-time algorithm
