स्तर समुच्चय (डेटा संरचनाएं)

कंप्यूटर विज्ञान में एक स्तर समुच्चय आँकड़े संरचना को अलग-अलग नमूने (सांख्यिकी) वाले गतिशील स्तर समुच्चय कार्यों का प्रतिनिधित्व करने के लिए बनाया गया है।

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

कालानुक्रमिक घटनाक्रम

1988 में स्टेनली ओशर और जेम्स सेथियन ने शक्तिशाली स्तर-समुच्चय विधि की प्रारंभ की थी। चूंकि, मानों के घने डी-आयामी सरणी आँकड़े संरचना के माध्यम से सीधा कार्यान्वयन $O(n^{d})$, जहाँ $n$ समय और भंडारण जटिलता दोनों में परिणाम देता है, डोमेन के स्थानिक विस्तार का प्रतिच्छेद अनुभागीय विश्लेषण है और $d$ डोमेन के स्थानिक आयामों की संख्या है।

संकीर्ण बैंड

1995 में एडालस्टीनसन और सेथियन द्वारा संकीर्ण बैंड स्तर समुच्चय विधि की प्रारंभ की थी अधिकांश संगणनाओं को इंटरफ़ेस के नजदीक के सक्रिय स्वरों के एक पतले बैंड तक सीमित कर दिया, इस प्रकार तीन आयामों में समय की जटिलता को $O(n^{2})$ तक कम कर दिया जाता है। सक्रिय स्वरों की सूची को फिर से बनाने के लिए संकीर्ण बैंड संरचना के आवधिक अद्यतन की आवश्यकता थी, जिसके लिए एक $O(n^{3})$ ऑपरेशन की आवश्यक थी जो पूरी मात्रा में स्वरों तक पहुँचा गया था इस संकीर्ण बैंड योजना के लिए संग्रहण जटिलता अभी भी $O(n^{3}).$ थी संकीर्ण बैंड डोमेन पर किनारा पर वैशिष्ट्य निर्माण के लिये समाधान को स्थिर करने के लिए सावधानीपूर्वक प्रक्षेप और डोमेन परिवर्तन योजनाओं की आवश्यकता होती है।

विरल क्षेत्र

यह $O(n^{3})$ समय की जटिलता को 1998 में व्हिटेकर द्वारा प्रस्तुत किए गए अनुमानित "विरल क्षेत्र" स्तर सेट पद्धति में समाप्त कर दिया गया था। इंटरफ़ेस के चारों ओर सक्रिय स्वरों को ट्रैक करने के लिए विरल क्षेत्र स्तर समुच्चय विधि लिंक्ड सूचियों के एक समुच्चय को नियोजित करती है। यह किसी भी महत्वपूर्ण ओवरहेड के बिना आवश्यकतानुसार सक्रिय क्षेत्र के वृद्धिशील विस्तार की अनुमति देता है। जबकि लगातार $O(n^{2})$ समय में कुशल, $O(n^{3})$ भंडारण स्थान अभी भी विरल क्षेत्र स्तर समुच्चय विधि द्वारा आवश्यक है। कार्यान्वयन के लिए विवरण देखे।

विरल खंड जाली

2003 में ब्रिडसन द्वारा विरल खंड जाली विधि की प्रारंभ की गई थी, $n^{3}$ आकार के पूरे बाउंडिंग ध्वनि को $m^{3}$ स्वर के छोटे घन खंडों में विभाजित करता है। आकार का एक मोटी जाली $(n/m)^{3}$ फिर पॉइंटर्स को केवल उन खंडो में संग्रहीत करता है जो स्तर समुच्चय के संकीर्ण बैंड को पार करते हैं। खंड आवंटन और डीलोकेशन घटित होते हैं क्योंकि सतह विकृतियों को समायोजित करने के लिए फैलती है। इस पद्धति में $O\left((nm)3+m^{3}n^{2}\right)$ एक उप-इष्टतम भंडारण जटिलता है , लेकिन सघन जालियो में निहित निरंतर समय पहुंच को बरकरार रखता है।

अष्टक

1999 में स्ट्रेन द्वारा प्रारंभ की गई ऑक्ट्री स्तर समुच्चय विधि और लोसासो, गिबू और फेडकीव द्वारा परिष्कृत, और हाल ही में मिन और गिबू द्वारा स्थिर घनक्षेत्र के पेड़ का प्रयोग करता है जिसमें पत्ती नोड्स में हस्ताक्षरित दूरी मान होते हैं। पर्याप्त उपर्युक्त प्राप्त करने के लिए वर्तमान में ऑक्ट्री स्तर के समुच्चय को इंटरफ़ेस (अर्थात् संकीर्ण बैंड) के साथ एक समान शोधन की आवश्यकता होती है। भंडारण के स्थितियो में यह प्रतिनिधित्व कुशल है, $O(n^{2}),$ और सक्रिय प्रश्नों के स्थितियो में अपेक्षाकृत कुशल, $O(\log \,n).$ ऑक्ट्री आँकड़े संरचनाओं पर स्तर विधि का एक लाभ यह है कि कोई आंशिक अंतर समीकरणों को हल कर सकता है जो विशिष्ट मुक्त सीमा समस्याओं से जुड़ा होता है जो स्तर समुच्चय पद्धति का प्रयोग करते हैं। सीएएसएल अनुसंधान समूह कम्प्यूटेशनल सामग्री, कम्प्यूटेशनल द्रव गतिकी, इलेक्ट्रोकाइनेटिक्स, छवि निर्देशित सर्जरी और नियंत्रण में काम की इस पंक्ति को विकसित किया है।

रन-लम्बाई एन्कोडेड

रन-लम्बाई एन्कोडिंग (आरएलई) स्तर समुच्चय विधि, 2004 में प्रस्तुत की गई, संकरे बैंड को पूर्ण सटीकता के साथ संग्रहीत करते समय संकीर्ण बैंड से दूर क्षेत्रों को केवल उनके संकेत प्रतिनिधित्व के लिए संपीड़ित करने के लिए RLE योजना लागू करता है। संकीर्ण बैंड का अनुक्रमिक ट्रैवर्सल इष्टतम है और ऑक्ट्री स्तर समुच्चय पर भंडारण दक्षता में और सुधार हुआ है। एक त्वरण लुकअप तालिका का जोड़ तेजी से $O(\log r)$ रैंडम सक्रिय की अनुमति देता है, जहां r प्रति क्रॉस सेक्शन रन की संख्या है। आरएलई योजना को एक आयामी पुनरावर्ती फैशन में लागू करके अतिरिक्त दक्षता प्राप्त की जाती है,नीलसन एंड मुसेथ के समान डीटी-ग्रिड द्वारा प्रारंभ की गई एक तकनीक है।

हैश तालिका स्थानीय स्तर समुच्चय

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

जैसा कि है, [...] एक चतुर्भुज डेटा संरचना स्तर-सेट कलन विधि के लिए हैश तालिका डेटा संरचना से अधिक अनुकूलित लगती है।

खराब दक्षता के तीन मुख्य कारण सूचीबद्ध हैं:

1. सटीक परिणाम प्राप्त करने के लिए, इंटरफ़ेस के करीब एक बड़े बैंड की आवश्यकता होती है, जो इंटरफ़ेस से दूर ग्रिड नोड्स की अनुपस्थिति का प्रतिकार करता है;
2. प्रदर्शन स्थानीय ग्रिड के बाहरी किनारों पर एक्सट्रपलेशन प्रक्रियाओं द्वारा बिगड़ जाते हैं
3. बैंड की चौड़ाई समय कदम को सीमित करती है और विधि को धीमा कर देती है।

बिंदु आधारित

2005 में कॉर्बेट पॉइंट-बेस्ड स्तर समुच्चय मेथड प्रस्तुत किया। स्तर समुच्चय के एक समान नमूने का प्रयोग करने के अतिरिक्त, निरंतर स्तर समुच्चय फ़ंक्शन को असंगठित बिंदु नमूनों के समुच्चय से कम से कम वर्गों के माध्यम से पुनर्निर्माण किया जाता है।

इस पेज में लापता आंतरिक लिंक की सूची

• स्तर सेट
• प्रतिपादन (कंप्यूटर ग्राफिक्स)
• वॉक्सेल
• रन-लेंथ एन्कोडिंग
• कम से कम वर्ग चल रहा है