पीएचडी → ज्यामिति → संगणकीय ज्यामिति ↓
कम्प्यूटेशनल ज्यामिति में उत्तल आवरण का परिचय
कम्प्यूटेशनल ज्यामिति के अध्ययन में, "उत्तल आवरण" की अवधारणा एक मूलभूत निर्माण खंड है। एक समतल पर बिखरे हुए बिंदुओं की कल्पना करें। उत्तल आवरण उन बिंदुओं के चारों ओर एक रबर बैंड लपेटने जैसा है। बैंड उस सबसे छोटे उत्तल बहुभुज का आकार ले लेगा जो सभी बिखरे हुए बिंदुओं को घेर सकता है।
उत्तल आकार की समझ
उत्तल आवरण में डूबने से पहले, यह समझना महत्वपूर्ण है कि उत्तलता का क्या मतलब है। एक आकार उत्तल होता है यदि आकार के अंदर के किसी भी दो बिंदुओं के लिए, उन्हें जोड़ने वाला रेखा खंड पूरी तरह से आकार के भीतर रहता है। इसे एक गुब्बारे की तरह सोचें। यदि आप गुब्बारे की सतह पर कहीं भी दो पिन चुभाते हैं और उन्हें धागे की एक टुकड़ी के साथ जोड़ते हैं, तो धागा गुब्बारे से बाहर नहीं फिसलता।
उत्तल आवरण की परिभाषा
बिंदुओं के सेट का उत्तल आवरण सबसे छोटा उत्तल सेट है जो सभी बिंदुओं को घेरता है। गणितीय रूप से, यदि आपके पास बिंदुओं का सेट S है, तो उत्तल आवरण उन सभी उत्तल सेटों का प्रतिच्छेदन है जो S को घेरते हैं। वैकल्पिक रूप से, यह एक सीमा है जो सभी बिंदुओं को घेरे रहते हुए न्यूनतम परिधि का उपयोग करता है।
गणितीय अभिव्यक्ति
बिंदुओं के सेट S का उत्तल आवरण निम्नलिखित रूप में दर्शाया जा सकता है:
उत्तल खोखला(S) = { x : x बिंदुओं की उत्तल संयोजन है S }
उत्तल आवरण का दृश्यकरण
उदाहरण 1: बुनियादी उत्तल आवरण
एक सरल परिदृश्य पर विचार करें जहां सेट में केवल तीन बिंदु होते हैं जो एक त्रिभुज बनाते हैं।
इस उदाहरण में, उत्तल आवरण स्वयं त्रिभुज है, क्योंकि इसके सभी तीन बिंदु इसके कोने हैं।
उदाहरण 2: एक अधिक जटिल सेट
कुछ अधिक जटिल बिंदुओं पर विचार करें:
यहां, बिंदु एक आकृति बनाते हैं जिसमें एक आंतरिक बिंदु शामिल होता है। उत्तल आवरण एक त्रिभुज है, (130, 80) के बिंदु को बाहर छोड़कर, जो आवरण की परिधि को प्रभावित नहीं करता है।
उत्तल आवरण के गुणधर्म
उत्तलता
आउटपुट आकार हमेशा उत्तल होता है, अर्थात प्रत्येक आंतरिक कोण 180 डिग्री से कम या बराबर होता है।
विशिष्टता
निर्दिष्ट बिंदुओं के लिए, उत्तल आवरण अद्वितीय होता है। यह अद्वितीयता इसलिए है क्योंकि उत्तलता की परिभाषा और यूक्लिडियन स्थान की प्रकृति के बीच कोई अंतर नहीं होता।
न्यूनतमता
उत्तल आवरण सेट के सभी बिंदुओं को घेरने वाली सबसे छोटी संभावित सीमा है।
उत्तल आवरण की गणना के लिए एल्गोरिद्म
विभिन्न एल्गोरिद्म बिंदुओं का सेट के उत्तल आवरण की गणना कर सकते हैं, प्रत्येक के अलग-अलग जटिलताएँ और उपयोग के मामले होते हैं। कुछ लोकप्रिय एल्गोरिद्म निम्नलिखित हैं:
उपहार आवरण एल्गोरिद्म
आमतौर पर जार्विस मार्च एल्गोरिद्म के रूप में जाना जाता है, यह किसी वस्त्र को लपेटने जैसा होता है, जिसमें आकृति के किनारे पर घूमना शामिल होता है।
1. सेट में सबसे बाएं बिंदु से प्रारंभ करें (सबसे छोटा x-निर्देशांक)। 2. उस बिंदु का चयन करें जो प्रारंभिक बिंदु द्वारा बनाई गई रेखा के साथ सबसे छोटा वामावर्त कोण बनाये। 3. कदम 2 को सबसे हाल ही में जोड़े गए बिंदु के साथ तब तक दोहराएं जब तक आप प्रारंभिक बिंदु तक न लौट जाएँ।
उपहार आवरण की गणनात्मक जटिलता आमतौर पर O(nh) होती है, जहां n इनपुट सेट में बिंदुओं की संख्या है, और h समाधान पर बिंदुओं की संख्या है।
ग्राहम स्कैन
यह एल्गोरिद्म पहले शीर्षों को क्रमबद्ध करके और फिर उन्हें एक के बाद एक विचार करके उत्तल आवरण की गणना करता है।
1. सबसे छोटे y-निर्देशांक वाले बिंदु को खोजें, सबसे छोटे x-निर्देशांक को छोड़ते हुए। 2. उन बिंदुओं को क्रम में उन के द्वारा बनाये गए कोण के बढ़ते क्रम में क्रमबद्ध करें और step 1 में चुने गए बिंदु के साथ x-अक्ष। 3. बिंदुओं को दोहराएं और उन बिंदुओं को हटाएं जो क्लॉकवाइज घुमाव पैदा करते हैं।
इसकी गणनात्मक जटिलता O(n log n) है, मुख्यतः प्रारंभिक क्रमबद्ध करने के कारण।
क्विकहुल एल्गोरिद्म
क्विकहुल एल्गोरिद्म विसंगटन-और-विजय की धारा पर आधारित एक विधि है।
1. न्यूनतम और अधिकतम x-निर्देशांक वाले बिंदुओं को खोजें, जो उत्तल आवरण का हिस्सा होना चाहिए। 2. एक आवर्तक विभाजन-और-विजय प्रक्रिया का उपयोग करें जो उस रेखा द्वारा परिभाषित दो बिंदुओं के प्रत्येक पक्ष पर उत्तल आवरण का निर्माण करने के लिए सेट बिंदुओं का निर्माण करता है।
औसत जटिलता O(n log n) है, जबकि सबसे खराब स्थिति में यह O(n^2) हो सकता है।
वृद्धिशील एल्गोरिद्म
इस एल्गोरिद्म में बिंदुओं को एक-एक करके जोड़ा जाता है और प्रत्येक चरण में उत्तल आवरण अपडेट किया जाता है।
1. प्रारंभ एक छोटे सेट बिंदुओं से करें जो प्रारंभिक आवरण बनाते हैं। 2. एक नया बिंदु जोड़ें और जांचें कि यह वर्तमान आच्छादन के अंदर है या नहीं। 3. अगर यह बाहर है, तो नए बिंदु को शामिल करने के लिए आवरण को अपडेट करें।
हालांकि बिग-ओ संकेतन के मामले में यह सबसे कुशल नहीं है, यह एल्गोरिद्म फिर भी कुछ विशिष्ट अनुप्रयोगों में सहज और उपयोगी हो सकता है।
उत्तल आवरण के अनुप्रयोग
उत्तल आवरण का कई व्यावहारिक अनुप्रयोग होते हैं:
कंप्यूटर ग्राफिक्स
कंप्यूटर ग्राफिक्स में वस्तुओं के एक सेट की सीमा का निर्धारण करने और टकराव का पता लगाने और पथ खोजने में प्रयुक्त होते हैं।
भौगोलिक विश्लेषण
जीआईएस प्रणालियों में, उत्तल आवरण भौगोलिक इकाइयों के समूह की परिभाषा में सहायता करते हैं।
पैटर्न की पहचान
पैटर्न की पहचान में समूहों के बिंदुओं का आकार देने में सहायता करने के लिए उपयोग किया जाता है, जो वर्गीकरण और पहचान में मदद करते हैं।
रोबोटिक्स
रोबोटिक्स में, उत्तल शेल्स प्रक्षेप पथिकरण और गति की योजना में सहायता प्रदान करते हैं, और अवरोधक के सेट के चारों ओर सुरक्षा पथ प्रदान करते हैं।
निष्कर्ष
उत्तल आवरण का अध्ययन अधिक जटिल कम्प्यूटेशनल ज्यामिति समस्याओं को समझने के लिए एक द्वार है। जबकि उनकी परिभाषा सरल है, कुशल गणना और अनुप्रयोग ज्यामिति और एल्गोरिद्म डिजाइन की गहरी समझ की आवश्यकता होती है। ज्यामिति के एक मौलिक पहलू के रूप में, उत्तल आवरण सक्रिय शोध का क्षेत्र बने रहते हैं और विभिन्न प्रौद्योगिकी अनुप्रयोगों में एक महत्वपूर्ण भूमिका निभाते हैं।
टिप्पणियाँ