सीमा क्षेत्र

For the planar problem, see सीमक वृत्त.

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

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

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

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

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

अनुप्रयोग

गुच्छन

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

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

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

एल्गोरिदम

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

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

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

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

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

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

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

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

रिटर का एल्गोरिदम $d$-आयामी स्थान में $n$ बिन्दु वाले निविष्ट पर समय $O(nd)$ में चलता है, जो इसे बहुत कुशल बनाता है। यद्यपि यह मात्र स्थूल परिणाम देता है जो सामान्यतः इष्टतम से 5% से 20% बड़ा होता है।

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

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

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

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

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

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