Space partitioning
ज्यामिति में, अंतरिक्ष विभाजन एक पूरे स्थान (आमतौर पर एक यूक्लिडियन स्थान) को दो या अधिक असंबद्ध उपसमुच्चय में विभाजित करने की प्रक्रिया है (एक समूह का विभाजन भी देखें)। दूसरे शब्दों में, स्थान विभाजन एक स्थान को गैर-अतिव्यापी क्षेत्रों में विभाजित करता है। अंतरिक्ष में किसी भी बिंदु को तब ठीक एक क्षेत्र में स्थित होने के लिए पहचाना जा सकता है। अवलोकन अंतरिक्ष-विभाजन प्रणालियाँ अक्सर पदानुक्रमित होती हैं, जिसका अर्थ है कि एक स्थान (या अंतरिक्ष का एक क्षेत्र) को कई क्षेत्रों में विभाजित किया जाता है, और फिर उसी अंतरिक्ष-विभाजन प्रणाली को इस प्रकार बनाए गए प्रत्येक क्षेत्र पर पुनरावर्ती रूप से लागू किया जाता है। क्षेत्रों को एक पेड़ में व्यवस्थित किया जा सकता है, जिसे अंतरिक्ष-विभाजन वृक्ष कहा जाता है। अधिकांश अंतरिक्ष-विभाजन प्रणालियाँ स्थान को विभाजित करने के लिए विमानों (या, उच्च आयामों में, हाइपरप्लेन) का उपयोग करती हैंः समतल के एक तरफ के बिंदु एक क्षेत्र बनाते हैं, और दूसरी तरफ के बिंदु दूसरे क्षेत्र का निर्माण करते हैं। समतल पर सटीक रूप से बिंदु आमतौर पर मनमाने ढंग से एक या दूसरी तरफ दिए जाते हैं। इस तरह से विमानों का उपयोग करके स्थान को बार-बार विभाजित करने से एक बी. एस. पी. वृक्ष उत्पन्न होता है, जो स्थान विभाजन के सबसे आम रूपों में से एक है। उपयोग कंप्यूटर ग्राफिक्स में अंतरिक्ष विभाजन विशेष रूप से कंप्यूटर ग्राफिक्स में महत्वपूर्ण है, विशेष रूप से किरण अनुरेखण में भारी उपयोग किया जाता है, जहां इसका उपयोग अक्सर आभासी दृश्य में वस्तुओं को व्यवस्थित करने के लिए किया जाता है। एक विशिष्ट दृश्य में लाखों बहुभुज हो सकते हैं। प्रत्येक के साथ एक किरण/बहुभुज प्रतिच्छेदन परीक्षण करना एक बहुत ही कम्प्यूटेशनल रूप से महंगा काम होगा। एक अंतरिक्ष-विभाजन डेटा संरचना (उदाहरण के लिए के-डी ट्री या बी. एस. पी. ट्री) में वस्तुओं को संग्रहीत करने से कुछ प्रकार के ज्यामिति प्रश्नों को करना आसान और तेज़ हो जाता है-उदाहरण के लिए यह निर्धारित करने में कि क्या एक किरण किसी वस्तु को काटती है, अंतरिक्ष विभाजन प्रतिच्छेदन परीक्षण की संख्या को केवल कुछ प्रति प्राथमिक किरण तक कम कर सकता है, जिससे बहुभुज की संख्या के संबंध में लघुगणक समय जटिलता प्राप्त होती है। अंतरिक्ष विभाजन का उपयोग अक्सर स्कैनलाइन एल्गोरिदम में कैमरे के देखने वाले फ्रस्टम से बहुभुज को खत्म करने के लिए किया जाता है, जिससे पाइपलाइन द्वारा संसाधित बहुभुज की संख्या सीमित हो जाती है। टकराव का पता लगाने में भी एक उपयोग हैः यह निर्धारित करना कि क्या दो वस्तुएं एक-दूसरे के करीब हैं, अंतरिक्ष विभाजन का उपयोग करके बहुत तेज हो सकता है। इंटीग्रेटेड सर्किट डिजाइन में, एक महत्वपूर्ण कदम डिजाइन नियम जांच है। यह कदम यह सुनिश्चित करता है कि पूरा किया गया डिजाइन विनिर्माण योग्य है। जाँच में ऐसे नियम शामिल होते हैं जो चौड़ाई और अंतराल और अन्य ज्यामिति पैटर्न को निर्दिष्ट करते हैं। एक आधुनिक डिजाइन में अरबों बहुभुज हो सकते हैं जो तारों और ट्रांजिस्टर का प्रतिनिधित्व करते हैं। कुशल जाँच ज्यामिति प्रश्न पर बहुत अधिक निर्भर करती है। उदाहरण के लिए, एक नियम निर्दिष्ट कर सकता है कि कोई भी बहुभुज किसी भी अन्य बहुभुज से कम से कम n नैनोमीटर का होना चाहिए। इसे सभी तरफ एक बहुभुज को n/2 से बड़ा करके और सभी प्रतिच्छेदन करने वाले बहुभुज खोजने के लिए एक ज्यामिति प्रश्न में परिवर्तित किया जाता है। संभाव्यता और सांख्यिकीय शिक्षण सिद्धांत में एक अंतरिक्ष विभाजन में घटकों की संख्या संभाव्यता सिद्धांत में कुछ परिणामों में एक केंद्रीय भूमिका निभाती है। अधिक जानकारी के लिए ग्रोथ फंक्शन देखें। भूगोल और जी. आई. एस. में कई अध्ययन और अनुप्रयोग हैं जहां भौगोलिक स्थानिक वास्तविकता को जल संबंधी मानदंडों, प्रशासनिक मानदंडों, गणितीय मानदंडों या कई अन्य द्वारा विभाजित किया जाता है। कार्टोग्राफी और जी. आई. एस.-भौगोलिक सूचना प्रणाली के संदर्भ में, मानक कोड द्वारा विभाजन की कोशिकाओं की पहचान करना आम बात है। उदाहरण के लिए हाइड्रोग्राफिक बेसिन और उप-बेसिन की पहचान करने वाले एच. यू. सी. कोड, देशों और उनके उपखंडों की पहचान करने वाले आई. एस. ओ. 3166-2 कोड, या मनमाने डी. जी. जी.-चतुर्थांश या स्थानों की पहचान करने वाले असतत वैश्विक ग्रिड। डेटा संरचनाएँ सामान्य अंतरिक्ष-विभाजन प्रणालियों में शामिल हैंः बी. एस. पी. पेड़ क्वाडट्रीस ऑक्ट्रीस के-डी पेड़ डिब्बे आर-पेड़ घटकों की संख्या मान लीजिए कि एन-आयामी यूक्लिडियन स्थान को हाइपरप्लेन द्वारा विभाजित किया गया है जो-आयामी हैं। विभाजन में घटकों की संख्या क्या है? घटकों की सबसे बड़ी संख्या तब प्राप्त होती है जब हाइपरप्लेन सामान्य स्थिति में होते हैं, यानी कोई भी दो समानांतर नहीं होते हैं और किसी भी तीन का प्रतिच्छेदन समान नहीं होता है। घटकों की इस अधिकतम संख्या को निरूपित करें। फिर, निम्नलिखित पुनरावृत्ति संबंध हैः-जब कोई आयाम नहीं होते हैं, तो एक ही बिंदु होता है। - जब कोई हाइपरप्लेन नहीं होते हैं, तो सारा स्थान एक घटक होता है। और इसका समाधान हैः यदि (उदाहरण के लिए)। लंबवत हाइपरप्लेन; प्रत्येक अतिरिक्त हाइपरप्लेन प्रत्येक मौजूदा घटक को 2 से विभाजित करता है)। जो ऊपरी सीमा में हैः द्विआधारी स्थान विभाजन असतत वैश्विक ग्रिड बहुभुज विभाजन टेसेलेशन संदर्भ कंप्यूटर ग्राफिक्स ज्यामितीय एल्गोरिदम भी देखें