मान लीजिए कि मेरे पास सामान्य स्थिति में एन लाइन सेगमेंट हैं। मैं अपने प्रत्येक एन सेगमेंट के लिए जल्दी से कैसे गिन सकता हूं, अन्य एन-1 कितने अंतर करता है?क्या लाइन सेगमेंट के दिए गए सेट के बीच चौराहे की संख्या गिनने का कोई प्रभावी तरीका है?
मैं ओ (एन) समय में यह नैतिक रूप से कर सकता हूं। मैं ओ ((एन + के) लॉग एन) में एक काफी सीधी स्वीप लाइन एल्गोरिदम (बेंटले-ओटमान) का उपयोग करके सभी चौराहे पा सकते हैं, जहां के ऐसे चौराहे की संख्या है, और उसके बाद मुझे एक चौराहे में मिले चौराहे को जोड़ना मायने रखता है।
मुझे की आवश्यकता नहीं है चौराहे, हालांकि; मैं सिर्फ यह जानना चाहता हूं कि कितने हैं। मैं नहीं देखता कि स्वीप लाइन एल्गोरिदम को तेज़ होने के लिए कैसे संशोधित किया जाए क्योंकि इसे प्रत्येक छेड़छाड़ के लिए पेड़ में दो चीजों को फिर से व्यवस्थित करने की आवश्यकता है, और मैं ऐसी किसी अन्य तकनीक के बारे में नहीं सोच सकता जो एक ही समस्या से पीड़ित नहीं है।
मुझे यह जानने में भी रूचि है कि कितने कुल चौराहे हैं।
मेरे पास है ... स्वीप लाइन विधि पर विश्वास करने में कठोर समय कम से कम पीटा जा सकता है। इस बात पर विचार करें कि मैं एन लाइन सेगमेंट के बीच चौराहे की संख्या गिन सकता हूं जिनके बाएं एंडपॉइंट्स में एक्स-समन्वय 0 है और जिनके दाएं एंडपॉइंट्स में एक्स-समन्वय 1 है; यह एक सरणी में उलटा गिनती की शास्त्रीय समस्या है। इसलिए, कम से कम कुछ विशेष मामलों में, मुझे इस तरह के प्रतिस्थापन की तलाश करने और किसी भी तरह इसका शोषण करने में सक्षम होना चाहिए। – tmyklebu
@tmyklebu, निश्चित रूप से, यदि कोई शोषक पदार्थ है, तो आप आसानी से इसका फायदा उठा सकते हैं। लेकिन आपको इसके बारे में पहले पता होना चाहिए। आप यूनिट स्क्वायर केस को 'ओ (एन)' में आसानी से देख सकते हैं, लेकिन यह मूर्खतापूर्ण होगा जब तक कि आपके पास विश्वास करने का अच्छा कारण न हो। (और इसी तरह अन्य विशेष मामलों के लिए, उत्तल बहुभुज के संग्रह की तरह।) ऐसे मामले "सामान्य मामला" नहीं हैं। बी-ओ बहुभुज के मामले को अच्छी तरह से संग्रहित करेगा, क्योंकि यह कम वास्तविक चौराहे के साथ गति करता है। – rici
बी-ओ उस मामले को संभालता है जहां केवल कुछ चौराहे अच्छी तरह से मौजूद हैं। मैं अभी भी किसी न किसी मामलों के साथ आ सकता हूं जब मुझे बहुभुज का गुच्छा मिला है (उसी बिंदु पर केंद्रित समतुल्य त्रिकोणों का एक पूरा गुच्छा चित्रित करें लेकिन यादृच्छिक कोणों से घिरा हुआ है)। विस्फोटक पदार्थ ... प्रश्न के बिंदु हैं ... :) Chazelle ("रिपोर्टिंग और गिनती सेगमेंट चौराहे") का एक पेपर है जो इस लंबवत अपघटन विचार का उपयोग करता है और मेरी समस्या के लिए ओ (एन 1.695) समय एल्गोरिदम प्राप्त करने के लिए purports, लेकिन ऐसा लगता है कि यह बहुत पर निर्भर करता है अव्यवहारिक डेटा संरचना। कुछ नहीं से बेहतर। – tmyklebu