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

Latest revision as of 10:45, 4 May 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$ बिन्दु वाले निविष्ट पर समय $O(nd)$ में चलता है, जो इसे बहुत कुशल बनाते है। यद्यपि यह मात्र स्थूल परिणाम देते है जो सामान्यतः इष्टतम से 5% से 20% बड़ा होता है।^{[citation needed]}

क्रोड-समुच्चय आधारित सन्निकटन

बदोइउ एट अल. ने सीमा क्षेत्र समस्या के लिए $1+\varepsilon$ सन्निकटन प्रस्तुत किया, जहाँ $1+\varepsilon$ सन्निकटन का अर्थ है कि निर्मित गोले में अधिकतम $(1+\varepsilon )r$ , ^[8] पर त्रिज्या है, जहाँ $r$ एक सीमा क्षेत्र का सबसे छोटा संभव त्रिज्या है।

क्रोड समुच्चय एक छोटा उपसमुच्चय है, कि उपसमुच्चय पर विलयन $1+\varepsilon$ पूरे समुच्चय का परिबद्ध क्षेत्र है। प्रत्येक पुनरावृत्ति में समुच्चय में सबसे दूर के बिंदु को जोड़कर क्रोडसमुच्चय का निर्माण वृद्धिशील रूप से किया जाता है।

कुमार एट अल. ने इस सन्निकटन एल्गोरिदम में सुधार किया^[9] यह समय $O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})$ में चले।

फिशर का यथार्थ हलकर्ता

फिशर एट अल. (2003) ने एक यथार्थ हलकर्ता प्रस्तावित किया, यद्यपि सबसे निकृष्टतम स्थिति में एल्गोरिदम में बहुपद चलने का समय नहीं है।^[10] एल्गोरिदम विशुद्ध रूप से संयोजी है और रैखिक प्रोग्रामन के लिए सरलीकृत विधि के समान एक धुरी योजना को लागू करते है, जिसका उपयोग पहले कुछ अनुमानों में किया गया था। यह एक बड़े गोले से प्रारम्भ होता है जो सभी बिंदुओं को आच्छादित करता है और धीरे-धीरे इसे तब तक सिकोड़ता है जब तक कि इसे और छोटा नहीं किया जा सकता है। एल्गोरिदम अध:पतन की स्थितियों में सही समापन नियम प्रस्तुत करती है, जिसे पूर्व लेखकों द्वारा अनदेखा किया जाता है; और आंशिक हलों का कुशल संचालन, जो एक प्रमुख गति-अप उत्पन्न करता है। लेखकों ने सत्यापित किया कि एल्गोरिदम कम और मध्यम रूप से निम्न (10,000 तक) आयामों में व्यवहार में कुशल है और अनुरोध करते है कि यह अपने चल बिन्दु संचालन में संख्यात्मक स्थिरता की समस्याओं को प्रदर्शित नहीं करते है।^[10] एल्गोरिदम का एक C++ कार्यान्वयन खुला स्त्रोत प्रोजेक्ट के रूप में उपलब्ध है।^[11]

परम बिंदु इष्टतम क्षेत्र

लार्सन (2008) सीमक स्फीयर समस्या को हल करने के लिए नियंत्रणीय गति से यथार्थता सन्निकटन के साथ "परम बिंदु इष्टतम क्षेत्र" विधि प्रस्तावित की। यह विधि $s$ दिशा सदिश का समुच्चय लेकर कार्य करती है और $s$ प्रत्येक सदिश पर सभी बिंदुओं को प्रक्षेपित करती है; गति-यथार्थता व्यापार-बंद चर के रूप में कार्य करते है। इन अनुमानों के $2s$ परम बिंदुओं पर एक यथार्थ हलकर्ता लगाए जाते है। एल्गोरिदम तब शेष बिंदुओं पर पुनरावृति करता है, यदि कोई हो, यदि आवश्यक हो तो गोले को बढ़ाना। बड़े $n$ के लिए यह विधि तुलनीय परिणाम देते हुए यथार्थ विधियों की तुलना में तीव्रता से परिमाण का क्रम है। इसमें $O(sn)$ का सबसे निकृष्टतम समय है।^[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
↑ Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), "Approximate clustering via core-sets" (PDF), Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, US: ACM, pp. 250–257, doi:10.1145/509907.509947, MR 2121149, S2CID 5409535
↑ 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
↑ ^10.0 ^10.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

बाहरी संबंध

Smallest Enclosing Circle Problem – describes several algorithms for enclosing a point set, including Megiddo's linear-time algorithm

[epos-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

[2] "Nimrod Megiddo's resume and publications".

[meg88-3] 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.

[chan18-4] 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.

[welzl92-5] 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

[6] CGAL 4.3 - Bounding Volumes - Min_sphere_of_spheres_d, retrieved 2014-03-30.

[Ritter1990-7] 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

[Badoiu2002-8] Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), "Approximate clustering via core-sets" (PDF), Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, US: ACM, pp. 250–257, doi:10.1145/509907.509947, MR 2121149, S2CID 5409535

[kumar2003-9] 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

[Fischer2003-10] 10.0 ^10.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

[11] -source project

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 39: / Line 39: @@
 === क्रोड-समुच्चय आधारित सन्निकटन ===
-बदोइउ एट अल. ने सीमा क्षेत्र समस्या के लिए <math>1+\varepsilon</math> सन्निकटन प्रस्तुत किया, जहाँ <math>1+\varepsilon</math> सन्निकटन का अर्थ है कि निर्मित गोले में अधिकतम <math>(1+\varepsilon)r</math>, पर त्रिज्या है, जहाँ <math>r</math> एक सीमा क्षेत्र का सबसे छोटा संभव त्रिज्या है।
+बदोइउ एट अल. ने सीमा क्षेत्र समस्या के लिए <math>1+\varepsilon</math> सन्निकटन प्रस्तुत किया, जहाँ <math>1+\varepsilon</math> सन्निकटन का अर्थ है कि निर्मित गोले में अधिकतम <math>(1+\varepsilon)r</math>, {{r|Badoiu2002}} पर त्रिज्या है, जहाँ <math>r</math> एक सीमा क्षेत्र का सबसे छोटा संभव त्रिज्या है।
 [[ कोर सेट |क्रोड समुच्चय]] एक छोटा उपसमुच्चय है, कि उपसमुच्चय पर विलयन <math>1+\varepsilon</math> पूरे समुच्चय का परिबद्ध क्षेत्र है। प्रत्येक पुनरावृत्ति में समुच्चय में सबसे दूर के बिंदु को जोड़कर क्रोडसमुच्चय का निर्माण वृद्धिशील रूप से किया जाता है।
@@ Line 161: / Line 161: @@
 == बाहरी संबंध ==
 * [http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm Smallest Enclosing Circle Problem] – describes several algorithms for enclosing a point set, including Megiddo's linear-time algorithm
-[[Category: ज्यामितीय एल्गोरिदम]] [[Category: क्षेत्रों]]
+[[Category:All articles with unsourced statements]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with unsourced statements from November 2015]]
 [[Category:Created On 24/04/2023]]
+[[Category:Harv and Sfn no-target errors]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with reference errors]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Template documentation pages|Short description/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 10:45, 4 May 2023

Contents

अनुप्रयोग

गुच्छन

एल्गोरिदम

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

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

क्रोड-समुच्चय आधारित सन्निकटन

फिशर का यथार्थ हलकर्ता

परम बिंदु इष्टतम क्षेत्र

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 10:45, 4 May 2023

अनुप्रयोग

गुच्छन

एल्गोरिदम

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

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

क्रोड-समुच्चय आधारित सन्निकटन

फिशर का यथार्थ हलकर्ता

परम बिंदु इष्टतम क्षेत्र

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories