सीमा क्षेत्र

For the planar problem, see Bounding circle.

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

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

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

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

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

अनुप्रयोग

क्लस्टरिंग

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

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

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

एल्गोरिदम

बाउंडिंग स्फेयर समस्या को हल करने के लिए सटीक और अनुमानित एल्गोरिदम हैं।

लीनियर प्रोग्रामिंग

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

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