बिंदु स्थान

बिंदु स्थान समस्या कम्प्यूटेशनल ज्यामिति का एक मौलिक विषय है। यह उन क्षेत्रों में अनुप्रयोग ढूंढता है जो ज्यामितीय डेटा प्रसंस्करण से संबंधित हैं: कंप्यूटर ग्राफिक्स, भौगोलिक सूचना प्रणाली(जीआईएस), गति योजना, और कंप्यूटर एडेड डिजाइन (सीएडी)।

अपने सबसे सामान्य रूप में, समस्या को अलग-अलग क्षेत्रों में स्थान का विभाजन दिया जाता है, जिससे उस क्षेत्र का निर्धारण किया जा सके जहां एक प्रश्न बिंदु स्थित है। एक उदाहरण अनुप्रयोग के रूप में, हर बार जब कोई वेब ब्राउज़र में किसी लिंक का अनुसरण करने के लिए माउस पर क्लिक करता है, तो हल की जाने वाली समस्या यह निर्धारित करना है कि कंप्यूटर स्क्रीन के किस क्षेत्र में माउस पॉइंटर घूम रहा है। बहुभुज समस्या में एक साधारण विशेष मामला एक बिंदु है। इस मामले में, किसी को यह निर्धारित करने की आवश्यकता है कि बिंदु एक बहुभुज की सीमा के अंदर, बाहर या सीमा पर है या नहीं।

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

प्लानर केस

डिब्बा का सीमा के अंदर एक प्लेनर सबडिवीजन

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

स्लैब अपघटन

स्लैब में विभाजित एक प्लानर उपखंड।

1976 में डोबकिन और लिप्टन द्वारा O(log n) समय प्राप्त करने के लिए सबसे सरल और सबसे पुरानी डेटा संरचना की खोज की गई थी। यह एस में प्रत्येक शीर्ष से गुजरने वाली लंबवत रेखाओं का उपयोग करके S को उप-विभाजित करने पर आधारित है। दो लगातार लंबवत रेखाओं के बीच के क्षेत्र को स्लैब कहा जाता है। ध्यान दें कि प्रत्येक स्लैब को गैर-प्रतिच्छेदी रेखा खंडों से विभाजित किया गया है जो स्लैब को बाएं से दाएं पूरी तरह से पार करते हैं। एक स्लैब के अंदर लगातार दो खंडों के बीच का क्षेत्र एस के एक अद्वितीय चेहरे से मेल खाता है। इसलिए, हम अपनी बिंदु स्थान समस्या को दो सरल समस्याओं में घटाते हैं:

1. ऊर्ध्वाधर स्लैब में समतल के उपविभाजन को देखते हुए, निर्धारित करें कि किस स्लैब में एक बिंदु है।
2. गैर-अंतर्विभाजक खंडों द्वारा क्षेत्रों में उप-विभाजित एक स्लैब को देखते हुए जो पूरी तरह से बाएं से दाएं स्लैब को पार करता है, निर्धारित करें कि किस क्षेत्र में एक बिंदु है।

पहली समस्या O(log n) समय में लंबवत रेखाओं के एक्स समन्वय पर द्विआधारी खोज द्वारा हल की जा सकती है। दूसरी समस्या को बाइनरी खोज द्वारा O(log n) समय में भी हल किया जा सकता है। यह देखने के लिए कि कैसे, ध्यान दें कि, चूंकि खंड एक दूसरे को नहीं काटते हैं और स्लैब को पूरी तरह से पार करते हैं, इसलिए खंडों को प्रत्येक स्लैब के अंदर लंबवत रूप से क्रमबद्ध किया जा सकता है।

जबकि यह एल्गोरिदम लघुगणकीय समय में बिंदु स्थान की अनुमति देता है और इसे लागू करना आसान है, स्लैब बनाने के लिए आवश्यक स्थान और स्लैब के भीतर निहित क्षेत्र O(n²) जितना ऊंचा हो सकता है, क्योंकि प्रत्येक स्लैब सेगमेंट के एक महत्वपूर्ण अंश को पार करता है।

कई लेखकों ने देखा है कि दो आसन्न स्लैबों को पार करने वाले वर्ग अधिकतर समान हैं। इसलिए, डेटा संरचना के आकार को महत्वपूर्ण रूप से कम किया जा सकता है। अधिक विशेष रूप से, सरनाक और टार्ज़न एक ऊर्ध्वाधर रेखा l को विमान के ऊपर बाएं से दाएं घुमाते हैं, जबकि एक निरंतर लाल-काले पेड़ में l को काटते हुए खंडों को बनाए रखते हैं। यह उन्हें O(log n) प्रश्नचिहन समय को बनाए रखते हुए स्टोरेज स्पेस को O(n) तक कम करने की अनुमति देता है।

मोनोटोन उपखंड

हाइलाइट किए गए कुछ मोनोटोन चेन के साथ एक मोनोटोन प्लानर सबडिवीजन।

ए (ऊर्ध्वाधर) मोनोटोन श्रृंखला एक पथ (ग्राफ सिद्धांत) है जैसे कि पथ के साथ वाई-निर्देशांक कभी नहीं बढ़ता है। एक साधारण बहुभुज (ऊर्ध्वाधर) मोनोटोन होता है यदि यह दो मोनोटोन श्रृंखलाओं द्वारा बनता है, जिसमें पहले और अंतिम शीर्ष समान होते हैं। सभी चेहरों को मोनोटोन बनाने के लिए, एक मोनोटोन उपखंड कहा जाता है, प्राप्त करने के लिए, कुछ किनारों को एक प्लेनर उपखंड में जोड़ना संभव है। यह प्रक्रिया उपखंड में किसी भी कोने को नहीं जोड़ती है (इसलिए, आकार O(n) रहता है), और O(n log n) समय में विमान झाडू द्वारा किया जा सकता है (यह बहुभुज त्रिभुज का उपयोग करके रैखिक समय में भी किया जा सकता है) ). इसलिए, सामान्यता का कोई नुकसान नहीं है, यदि हम अपनी डेटा संरचना को मोनोटोन उपखंडों के मामले में प्रतिबंधित करते हैं, जैसा कि हम इस खंड में करते हैं।

स्लैब अपघटन की कमजोरी यह है कि लंबवत रेखाएं अपघटन में अतिरिक्त खंड बनाती हैं, जिससे ओ (एन) भंडारण स्थान प्राप्त करना मुश्किल हो जाता है। हर्बर्ट एडल्सब्रूनर, लियोनिदास जे. गुइबास और जॉर्ज स्टॉल्फी ने एक इष्टतम डेटा संरचना की खोज की जो केवल एक मोनोटोन उपखंड में किनारों का उपयोग करती है। उपखंड को विभाजित करने के लिए ऊर्ध्वाधर रेखाओं का उपयोग करने के बजाय, ऊर्ध्वाधर मोनोटोन श्रृंखलाओं का उपयोग करने का विचार है।

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

पहले दो मुद्दों को कैसे हल किया जाए, इस पर विवरण इस लेख के दायरे से बाहर हैं। हम संक्षेप में उल्लेख करते हैं कि तीसरे मुद्दे को कैसे संबोधित किया जाए। बाइनरी खोज का उपयोग करके, हम परीक्षण कर सकते हैं कि ओ (लॉग एन) समय में एक बिंदु एक मोनोटोन श्रृंखला के बाएं या दाएं है या नहीं। जैसा कि हमें वास्तव में बिंदु स्थान निर्धारित करने के लिए ओ (लॉग एन) श्रृंखलाओं के माध्यम से एक और नेस्टेड बाइनरी खोज करने की आवश्यकता है, क्वेरी समय ओ (लॉग एन) है। ओ (लॉग एन) क्वेरी समय प्राप्त करने के लिए, हमें अलग-अलग मोनोटोन श्रृंखलाओं के किनारों के बीच पॉइंटर्स रखते हुए आंशिक कैस्केडिंग का उपयोग करने की आवश्यकता है।

त्रिकोण परिशोधन

त्रिभुज शोधन के क्रमिक चरण।

m शीर्षों वाले बहुभुज को m–2 त्रिभुजों में विभाजित किया जा सकता है। जिसे एक त्रिभुज से शुरू करते हुए गणितीय_इंडक्शन द्वारा दिखाया जा सकता है। बहुभुज त्रिकोणासन के लिए कुशलतापूर्वक कई एल्गोरिदम हैं, सबसे तेज़ ओ (एन) सबसे खराब समय है। इसलिए, हम अपने उपखंड के प्रत्येक बहुभुज को त्रिभुजों में विघटित कर सकते हैं, और अपनी डेटा संरचना को विशेष रूप से त्रिभुजों द्वारा गठित उपविभागों के मामले में प्रतिबंधित कर सकते हैं। किर्कपैट्रिक त्रिकोणीय उपखंडों में बिंदु स्थान के लिए O(n) संग्रहण स्थान और O(log n) क्वेरी समय के साथ एक डेटा संरचना देता है।

सामान्य विचार त्रिभुजों के पदानुक्रम का निर्माण करना है। एक क्वेरी करने के लिए, हम शीर्ष-स्तरीय त्रिकोण को खोजकर शुरू करते हैं जिसमें क्वेरी बिंदु होता है। चूँकि शीर्ष-स्तरीय त्रिभुजों की संख्या एक स्थिरांक से बंधी होती है, इसलिए यह संक्रिया O(1) समय में की जा सकती है। प्रत्येक त्रिभुज में त्रिकोण के संकेतक होते हैं जो पदानुक्रम के अगले स्तर में प्रतिच्छेद करते हैं, और संकेतकों की संख्या भी एक स्थिरांक से बंधी होती है। हम क्वेरी के साथ आगे बढ़ते हैं कि किस त्रिकोण में क्वेरी पॉइंट लेवल बाय लेवल है।

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

चतुर्भुज अपघटन

एक ट्रैपेज़ॉयडल अपघटन।

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

यह देखना आसान नहीं है कि बिंदु स्थान के लिए ट्रैपोज़ाइडल अपघटन का उपयोग कैसे किया जाए, क्योंकि स्लैब अपघटन में उपयोग की जाने वाली बाइनरी खोज के समान अब प्रदर्शन नहीं किया जा सकता है। इसके बजाय, हमें त्रिकोणीय परिशोधन दृष्टिकोण के समान ही एक प्रश्न का उत्तर देने की आवश्यकता है, लेकिन डेटा संरचना ऊपर-नीचे बनाई गई है। प्रारंभ में, हम एक ट्रैपेज़ॉयडल अपघटन बनाते हैं जिसमें केवल बाउंडिंग बॉक्स होता है, और कोई आंतरिक वर्टेक्स नहीं होता है। फिर, हम उपखंड से खंडों को एक-एक करके, यादृच्छिक क्रम में जोड़ते हैं, समलम्बाकार अपघटन को परिष्कृत करते हुए। पिछले विश्लेषण का उपयोग करके, हम दिखा सकते हैं कि प्रत्येक सम्मिलन के लिए बनाए गए ट्रैपेज़ोइड्स की अपेक्षित संख्या एक स्थिरांक से बंधी है।

हम एक निर्देशित विश्वकोश ग्राफ का निर्माण करते हैं, जहाँ कोने शोधन में किसी बिंदु पर मौजूद ट्रेपेज़ॉइड होते हैं, और निर्देशित किनारे उपखंड द्वारा प्राप्त ट्रेपेज़ोइड्स को जोड़ते हैं। इस डिग्राफ में एक खोज की अपेक्षित गहराई, बाउंडिंग बॉक्स के अनुरूप शीर्ष से शुरू होती है, O(log n) है.

उच्च आयाम

2 से बड़े आयामों के लिए रैखिक स्थान और लॉगरिदमिक क्वेरी समय के साथ कोई ज्ञात सामान्य बिंदु स्थान डेटा संरचना नहीं है. इसलिए, हमें या तो क्वेरी समय, या संग्रहण स्थान का त्याग करना होगा, या खुद को कुछ कम सामान्य प्रकार के उपखंडों तक सीमित रखना होगा।

त्रि-आयामी स्थान में, O(n log n) स्थान का उपयोग करके O(log² n) में बिंदु स्थान प्रश्नों का उत्तर देना संभव है। सामान्य विचार कई प्लानर पॉइंट स्थान डेटा संरचनाओं को बनाए रखना है, जो उपखंड के चौराहे के अनुरूप एन समांतर विमानों के साथ होता है जिसमें प्रत्येक उपखंड वर्टेक्स होता है। इस विचार का एक सरल उपयोग भंडारण स्थान को O(n²) तक बढ़ा देगा। स्लैब अपघटन के समान ही, स्टोरेज स्पेस को O (n log n) तक कम करने के लिए लगातार डेटा संरचनाओं के बीच समानता का शोषण किया जा सकता है, लेकिन क्वेरी समय O (log² n) तक बढ़ जाता है। डी-डायमेंशनल स्पेस में, पॉइंट लोकेशन को चेहरों को (डी-1) -डायमेंशनल स्पेस में रिकर्सिवली प्रोजेक्ट करके हल किया जा सकता है। जबकि क्वेरी समय O(log n) है, संग्रहण स्थान जितना अधिक हो सकता है $O(n^{2^{d}})$. डी-आयामी डेटा संरचनाओं की उच्च जटिलता ने विशेष प्रकार के उपखंडों का अध्ययन किया।

हाइपरप्लेन की व्यवस्था का मामला एक महत्वपूर्ण उदाहरण है। एन हाइपरप्लेन की व्यवस्था ओ (एन) को परिभाषित करती है^d) सेल, लेकिन बिंदु स्थान O(n) के साथ O(log n) समय में किया जा सकता है^d) बर्नार्ड चाज़ेल की श्रेणीबद्ध कटिंग (ज्यामिति) का उपयोग करके स्थान।

एक अन्य विशेष प्रकार के उपखंड को रेक्टिलिनियर (या ऑर्थोगोनल) उपखंड कहा जाता है। एक आयताकार उपखंड में, सभी किनारे डी ऑर्थोगोनल अक्ष में से एक के समानांतर होते हैं। इस स्थिति में, बिंदु स्थान का उत्तर O(log^d-1 n) समय O(n) स्थान के साथ।

संदर्भ

• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000). "Chapter 6: Point location". Computational Geometry (2nd revised ed.). Springer-Verlag. pp. 121–146. ISBN 3-540-65620-0.
• Dobkin, David; Lipton, Richard J. (1976). "Multidimensional searching problems". SIAM Journal on Computing. 5 (2): 181–186. doi:10.1137/0205015.
• Snoeyink, Jack (2004). "Chapter 34: "Point Location". In Goodman, Jacob E.; O'Rourke, Joseph (eds.). Handbook of Discrete and Computational Geometry (2nd ed.). Chapman & Hall/CRC. ISBN 1-58488-301-4.
• Sarnak, Neil; Tarjan, Robert E. (1986). "Planar point location using persistent search trees". Communications of the ACM. 29 (7): 669–679. doi:10.1145/6138.6151.
• Edelsbrunner, Herbert; Guibas, Leonidas J.; Stolfi, Jorge (1986). "Optimal point location in a monotone subdivision". SIAM Journal on Computing. 15 (2): 317–340. doi:10.1137/0215023.
• Kirkpatrick, David G. (1983). "Optimal search in planar subdivisions". SIAM Journal on Computing. 12 (1): 28–35. CiteSeerX 10.1.1.461.1866. doi:10.1137/0212002.

बाहरी संबंध

• Point-Location Source Repository at Stony Brook University
• Point-Location Queries in CGAL, the Computational Geometry Algorithms Library