सीमा क्षेत्र

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

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

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

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

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

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

फिशर का यथार्थ सॉल्वर

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

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

Larsson (2008) सीमक स्फीयर समस्या को हल करने के लिए यथार्थता सन्निकटन के लिए नियंत्रणीय गति के साथ एक्सट्रीमल पॉइंट्स ऑप्टीमल क्षेत्र विधि प्रस्तावित की। यह विधि का एक समुच्चय लेकर काम करती है $s$ दिशा वैक्टर और प्रत्येक वेक्टर पर सभी बिंदुओं को प्रोजेक्ट करना $s$; $s$ गति-यथार्थता व्यापार-बंद चर के रूप में कार्य करता है। एक यथार्थ सॉल्वर पर लागू होता है $2s$ इन अनुमानों के चरम बिंदु। एल्गोरिदम तब शेष बिंदुओं पर पुनरावृति करता है, यदि कोई हो, यदि आवश्यक हो तो गोले को बढ़ाना। बड़े के लिए $n$ तुलनात्मक परिणाम देते हुए, यह विधि यथार्थ विधियों की तुलना में परिमाण के क्रम में तीव्री से है। इसका सबसे खराब समय है $O(sn)$।

यह भी देखें

• सीमक मात्रा
• परिबद्ध गोला, परिबद्ध वृत्त

बाहरी संबंध

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