Kinetic convex hull
एक गतिज उत्तल पतवार डेटा संरचना एक गतिज डेटा संरचना है जो लगातार चलने वाले बिंदुओं के एक समूह के उत्तल पतवार को बनाए रखती है। इसे गतिशील उत्तल पतवार डेटा संरचनाओं से अलग किया जाना चाहिए, जो निरंतर गति के बजाय बिंदुओं के सम्मिलन या विलोपन जैसे असतत परिवर्तनों से गुजरने वाले बिंदुओं को संभालते हैं। 2डी केस 2-आयामी उत्तल पतवार समस्या के लिए सबसे प्रसिद्ध डेटा संरचना बास्च, गुइबास और हर्शबर्गर द्वारा बनाई गई है। यह डेटा संरचना प्रतिक्रियाशील, कुशल, संक्षिप्त और स्थानीय है। डेटा संरचना बिंदुओं के एक समूह के उत्तल पतवार का दोहरा रेखाओं के दोहरे समूह के ऊपरी और निचले लिफाफे हैं। इसलिए, चलती रेखाओं के एक समूह के ऊपरी और निचले लिफाफों को बनाए रखना गतिशील बिंदुओं के एक समूह के उत्तल पतवार को बनाए रखने के बराबर है। ऊपरी और निचले लिफाफों की गणना करना समतुल्य समस्याएं हैं, इसलिए रेखाओं के एक समूह के ऊपरी लिफाफे की गणना करना गतिशील बिंदुओं के एक समूह के उत्तल पतवार की गणना करने के बराबर है। स्थैतिक रेखाओं के एक समूह के ऊपरी लिफाफे की गणना एक विभाजन और विजय एल्गोरिथ्म का उपयोग करके की जा सकती है जो रेखाओं को समान आकार के दो सेटों में विभाजित करता है, अपने ऊपरी लिफाफों को खोजने के लिए खुद को दो सेटों पर पुनरावर्ती रूप से बुलाता है, और फिर दोनों परिणामी ऊपरी लिफाफों को मिला देता है। विलय चरण एक ऊर्ध्वाधर रेखा स्वीप का उपयोग करके किया जाता है। अंकों के पहले सेट को नीला और दूसरे सेट को लाल कहें। ऊपरी लिफाफों के विलय के लिए मानक लाइन स्वीप एल्गोरिथ्म लाल और नीले ऊपरी लिफाफों के सभी शीर्षों को बाएं से दाएं की ओर ले जाता है। सबसे हाल ही में सामना किए गए लाल और नीले बिंदुओं को लाइन स्वीप के रूप में बनाए रखा जाता है। जब एक बिंदु का सामना किया जाता है, तो एल्गोरिथ्म जांच करता है कि क्या बिंदु विपरीत रंग के अंतिम सामना किए गए बिंदु के बाद खंड के ऊपर या नीचे है। यदि यह ऊपर है, तो उस बिंदु को विलय किए गए ऊपरी लिफाफे में जोड़ा जाता है। यदि यह अंतिम जोड़े गए बिंदु से अलग रंग का है, तो लाल और नीले लिफाफे पार हो गए हैं, इसलिए प्रतिच्छेदन बिंदु को भी विलय किए गए ऊपरी लिफाफे में जोड़ा जाता है। इस एल्गोरिथ्म के परिणामस्वरूप किनारों और शीर्षों का अनुक्रम केवल बिंदुओं के क्रम और रेखा-बिंदु तुलना के परिणामों पर निर्भर करता है। इस प्रकार, परिणाम को निम्नलिखित प्रमाणपत्रों के साथ प्रमाणित किया जा सकता हैः x-प्रमाण पत्र () का उपयोग लाल और नीले लिफाफों के शीर्षों के क्रम को प्रमाणित करने के लिए किया जाता है। वे शीर्षों के समूह पर एक गतिज क्रमबद्ध सूची के लिए प्रमाण पत्र हैं। चूँकि प्रत्येक अंक में 2 पंक्तियाँ शामिल होती हैं, और प्रमाणपत्र में 2 अंक शामिल होते हैं, प्रत्येक प्रमाणपत्र में 4 पंक्तियाँ शामिल होती हैं। y-प्रमाणपत्र () का उपयोग यह प्रमाणित करने के लिए किया जाता है कि एक शीर्ष एक किनारे के ऊपर या नीचे है। एल्गोरिदम के दौरान होने वाली सभी तुलनाओं के लिए प्रमाण पत्र दिखाई देते हैं। जब तक ये सभी प्रमाण पत्र हैं, विलय चरणों को समान रूप से निष्पादित किया जाएगा, इसलिए परिणामी ऊपरी लिफाफा समान होगा। स्थैतिक ऊपरी लिफाफा एल्गोरिदम को प्रमाणित करने के लिए इन प्रमाणपत्रों का उपयोग करके ऊपरी लिफाफों के लिए एक गतिज डेटा संरचना बनाई जा सकती है। हालाँकि, यह योजना स्थानीय नहीं है, क्योंकि एक पंक्ति कई वाई-प्रमाण पत्रों में शामिल होती है यदि यह ऊपर या नीचे रहती है तो दूसरे लिफाफे से कई बिंदु सामने आते हैं। इस प्रकार, एक एस-प्रमाण पत्र () प्रस्तुत करना आवश्यक है जो प्रमाणित करता है कि एक रेखा का ढलान दूसरी रेखा के ढलान से अधिक या कम है। सभी अंकों के लिए निम्नलिखित प्रमाण पत्र होना एक विलय के परिणामस्वरूप किनारों और शीर्षों के अनुक्रम को प्रमाणित करने के लिए पर्याप्त है, जिसमें प्रति पंक्ति केवल ओ (1) प्रमाण पत्र हैंः यह अपनी दाहिनी ओर के निकटतम शीर्ष को दर्शाता है। यह प्रमाणपत्र उन सभी अंकों के लिए संग्रहीत किया जाता है जिनका बिंदु से अलग रंग होता है, जो उनके बाद आता है। : या। यह प्रमाणपत्र सभी बिंदुओं के लिए संग्रहीत किया जाता है जैसे कि प्रतिच्छेदन। प्रतिद्वंद्वी के किनारे को दर्शाता है, दूसरे लिफाफे का किनारा जो ऊपर या नीचे है। : या। यह प्रमाणपत्र सभी बिंदुओं के लिए संग्रहीत किया जाता है जैसे कि प्रतिच्छेदन। :. यह प्रमाणपत्र उन सभी अंकों के लिए संग्रहीत किया जाता है जिनके लिए और। :. यह प्रमाणपत्र उन सभी अंकों के लिए संग्रहीत किया जाता है जिनके लिए और। :. यह प्रमाणपत्र उन सभी अंकों के लिए संग्रहीत किया जाता है जिनके लिए और। :. यह प्रमाणपत्र उन सभी अंकों के लिए संग्रहीत किया जाता है जिनके लिए और। :. यह प्रमाणपत्र उन सभी अंकों के लिए संग्रहीत किया जाता है जिनके लिए और। पहला प्रमाणपत्र, लाल और नीले लिफाफों में अंकों के एक्स-ऑर्डर को प्रमाणित करता है। दूसरे और तीसरे प्रमाण पत्र, और, लाल और नीले लिफाफों के चौराहों को प्रमाणित करते हैं। शेष 5 प्रमाणपत्र,,,, और उन किनारों को रखें जो ऊपरी लिफाफों में नहीं हैं, किनारों की ढलानों के क्रम में जो इसके ऊपर हैं। यदि ढलान अनुक्रम के प्रारंभ या अंत में है, या इसे प्रमाणित करें। यदि यह अनुक्रम के बीच में है, और इसे प्रमाणित करता है, और प्रमाणित करता है कि दो रेखाओं का प्रतिच्छेदन बिंदु कि किनारे की ढलान बीच में है, उसके ऊपर है। ये एक या तीन प्रमाण पत्र यह साबित करने के लिए पर्याप्त हैं कि सभी किनारे इस रेखा के ऊपर हैं। पिछली योजना के विपरीत सभी पंक्तियाँ केवल निरंतर संख्या में प्रमाणपत्रों में शामिल होती हैं। जब भी इनमें से प्रमाणपत्र विफल हो जाते हैं, तो विलय किए गए लिफाफे और प्रमाणपत्रों को ओ (1) समय में अद्यतन किया जा सकता है। उत्तल पतवार के लिए गतिज डेटा संरचना का निर्माण इन प्रमाणपत्रों का उपयोग करके ऊपरी लिफाफों के पुनरावर्ती विलय को प्रमाणित करने के लिए किया जाता है। जब भी प्रमाण पत्र विफल हो जाते हैं, तो उनके विलय को अद्यतन किया जाता है, और यदि विलय के परिणामस्वरूप लिफाफा बदल जाता है, तो परिवर्तनों को उन सभी विलयों के माध्यम से प्रचारित किया जाता है जो विलय के परिणाम पर निर्भर करते हैं। प्रदर्शन यह डेटा संरचना प्रतिक्रियाशील, स्थानीय, संक्षिप्त और कुशल है। यह ऊपरी लिफाफे को प्रमाणित करने के लिए उपयोग किए जाने वाले विलय की लघुगणक गहराई के कारण होता है। उत्तरदायीः जब कोई प्रमाणपत्र विफल हो जाता है, तो उसके द्वारा प्रमाणित विलय को ठीक करने में ओ (1) लगता है। यदि परिणामी लिफाफा बदलता है, तो परिवर्तन को उन सभी विलयों तक प्रचारित किया जाना चाहिए जो बदले हुए विलय के परिणाम पर निर्भर करते हैं। ओ (लॉग एन) ऐसे विलय हैं, इसलिए अद्यतन कुल ओ (लॉग एन) समय में किया जा सकता है। स्थानीयः प्रत्येक पंक्ति अधिकांश ओ (लॉग एन) प्रमाणपत्रों में शामिल होती है। ऐसा इसलिए है क्योंकि प्रत्येक पंक्ति प्रत्येक विलय में प्रमाण पत्रों की एक स्थिर संख्या में शामिल होती है, और प्रत्येक पंक्ति ओ (लॉग एन) विलय कुल में होती है। कॉम्पैक्टनेसः इस डेटा संरचना में उपयोग किए जाने वाले प्रमाणपत्रों की अधिकतम संख्या ओ (एन लॉग एन) है। ऐसा इसलिए है क्योंकि प्रत्येक विलय में कई प्रमाण पत्र शामिल होते हैं जो विलय की गई रेखाओं की संख्या के लिए रैखिक होते हैं। एन पंक्तियों के ऊपरी लिफाफे को प्रमाणित करने के लिए एन/2 पंक्तियों के दो उपसमुच्चय के विलय ऊपरी लिफाफे के लिए प्रमाण पत्र और लिफाफों के विलय के लिए प्रमाण पत्र की आवश्यकता होती है। इस प्रकार एन पंक्तियों के ऊपरी लिफाफे को प्रमाणित करने के लिए आवश्यक प्रमाणपत्रों की संख्या, सी (एन), सी (1) = ओ (1) के साथ पुनरावृत्ति सी (एन) = 2सी (एन/2) + ओ (एन) को संतुष्ट करती है। विभाजन और विजय पुनरावृत्तियों के लिए मास्टर प्रमेय के अनुसार, सी (एन) = ओ (एन लॉग एन)। दक्षताः बीजगणितीय या छद्म-बीजगणितीय प्रक्षेपवक्रों पर इस एल्गोरिथ्म द्वारा संसाधित घटनाओं की अधिकतम संख्या सभी के लिए लगभग द्विघात है। रैखिक रूप से चलने वाले बिंदुओं के उत्तल पतवार समय बदल सकते हैं। इस प्रकार यह डेटा संरचना कुशल है। उच्च आयाम 2 से अधिक आयामों में गतिशील बिंदुओं के उत्तल पतवार को बनाए रखने के लिए एक कुशल गतिज डेटा संरचना खोजना एक खुली समस्या है। संबंधित समस्याएं गतिज उत्तल पतवार का उपयोग निम्नलिखित संबंधित समस्याओं को हल करने के लिए किया जा सकता हैः गतिज व्यास गतिज चौड़ाई गतिज न्यूनतम बॉक्स गतिज सबसे छोटी संलग्न डिस्क संदर्भ गतिज डेटा संरचनाएं कन्वेक्स पतवार एल्गोरिदम