Kinetic closest pair
एक गतिज निकटतम जोड़ी डेटा संरचना एक गतिज डेटा संरचना है जो अंकों की निकटतम जोड़ी को बनाए रखती है, जो एक मीट्रिक स्थान में समय के साथ लगातार आगे बढ़ रहे n बिंदुओं का एक सेट P है। जबकि स्थिर मामले में कई कुशल एल्गोरिदम ज्ञात थे, उन्हें गतिमान करना कठिन साबित हुआ, इसलिए इस समस्या को हल करने के लिए नए स्थिर एल्गोरिदम विकसित किए गए। 2डी केस अप्रोच 1 निकटतम जोड़ी के रखरखाव के लिए सबसे सरल गतिज दृष्टिकोण डेलाउने त्रिकोण के रूपों का उपयोग करना है। एक षट्कोण पर विचार करें और इसे छह समबाहु त्रिभुजों में विभाजित करें, और फिर प्रत्येक समबाहु त्रिभुज के आधार पर एक डेलॉने त्रिभुज बनाएँ, क्योंकि प्रत्येक एक उत्तल आकार है। इन छह डिलाउने त्रिकोणों का संयोजन, जिसे समबाहु डिलाउने ग्राफ (ईडीजी) कहा जाता है, निकटतम पड़ोसी ग्राफ (एन. एन. जी.) के लिए एक सुपरग्राफ है; ईडीजी में न्यूनतम लंबाई वाले किनारे के अंतिम बिंदु निकटतम जोड़ी देते हैं। उत्तल आकृतियों के आधार पर डेलाउने त्रिकोणों को बनाए रखना सीधा है। समय के साथ ईडीजी को देखते हुए, ईडीजी के किनारों पर एक गतिज टूर्नामेंट ट्री बनाकर, कोई भी आसानी से निकटतम जोड़ी को बनाए रख सकता है। यह निकटतम जोड़ी के. डी. एस. कुशल, परिशोधन प्रतिक्रियाशील और कॉम्पैक्ट है, लेकिन सामान्य रूप से स्थानीय नहीं है। निम्नलिखित दृष्टिकोण निकटतम जोड़ी के रखरखाव के लिए एक स्थानीय के. डी. एस. प्रस्तुत करता है। दृष्टिकोण 2 दूसरा गतिज दृष्टिकोण निम्नलिखित टिप्पणियों पर आधारित है। विभाजित करें और जीतें यदि एक बिंदु के आसपास की जगह को कोणीय रूप से छह "वेज" में विभाजित किया जाता है, प्रत्येक चौड़ा, निकटतम बिंदु प्रत्येक वेज में निकटतम बिंदुओं में से निकटतम है। इस लेख का शेष भाग "मुख्य" वेज (जो एक्स-अक्ष द्वारा विभाजित हैं) पर ध्यान केंद्रित करेगा, और समतल को घुमाने के बाद सममित तर्क अन्य वेज पर लागू होंगे। मिलान अंक अंक और "मिलान" कहा जाता है यदि वे एक दूसरे के निकटतम अंक हैं। स्पष्ट रूप से, अंकों की निकटतम जोड़ी एक मिलान जोड़ी है। बिंदुओं पर विचार करें और, जैसे कि बाईं ओर है और ऊपर वर्णित केंद्र में वेज में स्थित है। यदि निकटतम बिंदु है, तो x-दिशा में निकटतम बिंदु (इस वेज में) होना चाहिए। इस प्रकार, एक्स-दिशा में निकटतम बिंदुओं के जोड़े (इस वेज के भीतर) का सेट निकटतम बिंदुओं के जोड़े के सेट का एक सुपरसेट है। सेट पी में प्रत्येक बिंदु पी = (एक्स, वाई) को एक नए बिंदु पर मानचित्रित करें, जिससे परिवर्तित बिंदुओं का सेट पी 'बनता है। ध्यान दें कि एक बिंदु के लिए, "मुख्य" वेजों में बिंदु इस नई समन्वय प्रणाली की तुलना में या तो बड़े या छोटे होते हैं और निर्देशांक होते हैं। बिंदुओं को x, u और v निर्देशांकों द्वारा क्रमबद्ध करें, और उन्हें गतिज क्रमबद्ध सूचियों में संग्रहीत करें। अंदर के बिंदुओं पर 2डी रेंज ट्री टी बनाएँ। प्राथमिक वृक्ष में प्रत्येक नोड डब्ल्यू के लिए, मान लीजिए कि टी (डब्ल्यू) डब्ल्यू से जुड़ा द्वितीयक वृक्ष है। इस रेंज ट्री का उपयोग एक बिंदु के लिए "मुख्य" वेज में बिंदुओं की पहचान करने के लिए किया जाएगा। प्राथमिक वृक्ष में प्रत्येक नोड डब्ल्यू के लिए, और टी (डब्ल्यू) में प्रत्येक नोड ई के लिए, जोड़ी (डब्ल्यू, ई) = (बी, आर) की गणना करें, जहां बी (या आर) को ई के बाएं (या दाएं) उप-वृक्ष में अधिकतम (या न्यूनतम) एक्स-समन्वय के साथ बिंदु के रूप में परिभाषित किया गया है। मान लीजिए कि सभी जोड़े डब्ल्यू, ई, टी के लिए (डब्ल्यू, ई) का सेट हो। यह निकटतम बिंदुओं के जोड़े (मुख्य वेज के भीतर) के सेट का एक सुपरसेट है। जोड़ी में बिंदुओं के बीच की दूरी (मूल समन्वय प्रणाली में मापा गया) द्वारा निर्धारित प्राथमिकताओं के साथ जोड़े पर एक गतिज प्राथमिकता कतार बनाएँ। क्रमशः गतिज प्राथमिकता कतारों को चालू करने के लिए, विमान को घुमाने के लिए उपरोक्त चरणों को दोहराएं। पी में अंकों की निकटतम जोड़ी उपरोक्त तीन प्राथमिकता कतारों से प्राप्त न्यूनतम न्यूनतम से मेल खाती है। रखरखाव प्रमाणपत्र विफलताएं प्राथमिकता वाली कतारों और क्रमबद्ध सूचियों में हो सकती हैं। अंकों के क्रम में अदला-बदली टी में परिवर्तन का कारण बनेगी (जिसमें समय लगेगा), और प्राथमिकता वाली कतारों में सम्मिलन/विलोपन का कारण बन सकती है। ध्यान दें कि ऊपर परिभाषित किए गए सेटों में परिवर्तनों की संख्या एक स्थिर संख्या होने की आवश्यकता नहीं है। हालांकि, कोई भी जोड़ी जो पी और क्यू परिवर्तन के क्रम के परिणामस्वरूप मिलान करना शुरू या बंद कर देती है, उसमें पी और/या क्यू होना चाहिए, और इसलिए केवल मिलान किए गए जोड़े की एक स्थिर संख्या होती है जिन्हें प्राथमिकता कतारों में डाला/हटाया जाना चाहिए। केवल इन मेल खाने वाले जोड़े को अद्यतन करना ठीक है क्योंकि परिभाषा के अनुसार, केवल मेल खाने वाले जोड़े के पास निकटतम जोड़ी होने का मौका होता है। विश्लेषण यह के. डी. एस. हैः प्रतिक्रियाशीलः एक घटना को संसाधित करने में समय लगता है स्थानीयः चूंकि प्रत्येक बिंदु गतिज क्रमबद्ध सूचियों और गतिज प्राथमिकता कतारों की एक स्थिर संख्या में मौजूद होता है, इसलिए स्थान उन संरचनाओं के स्थान से अनुसरण करता है कॉम्पैक्टनेसः गतिज क्रमबद्ध सूचियों और गतिज प्राथमिकता कतारों की कॉम्पैक्टनेस से कॉम्पैक्टनेस का अनुसरण करता है कुशलः क्रमबद्ध सूचियों में प्रत्येक अदला-बदली गतिज प्राथमिकता कतारों में निरंतर संख्या में सम्मिलन और विलोपन का कारण बनती है। यह मानते हुए कि बिंदुओं की गति छद्म-बीजगणितीय है, अदला-बदली की एक बहुपद संख्या है, और इसलिए इस के. डी. एस. द्वारा घटनाओं की एक बहुपद संख्या को संसाधित किया जाता है, जिससे यह कुशल हो जाता है। संदर्भ गतिज डेटा संरचनाएँ ज्यामितीय डेटा संरचनाएँ