त्रिभुज विभाजन

Question

यह 2010 प्रशांत एसीएम-आईसीपीसी प्रतियोगिता में एक समस्या थी। इसका अर्थ त्रिभुज के अंदर बिंदुओं के एक सेट को तीन subtriangles में विभाजित करने का एक तरीका खोजने का प्रयास कर रहा है जैसे कि प्रत्येक विभाजन में अंक का एक तिहाई हिस्सा होता है।

इनपुट: बाउंडिंग त्रिकोण का

• निर्देशांक: (v1x,v1y),(v2x,v2y),(v3x,v3y)
• अनेक 3n < 30000 त्रिकोण
• 3n अंकों की निर्देशांक अंदर झूठ बोल अंकों की संख्या का प्रतिनिधित्व: (x_i,y_i) के लिए i=1...3n

आउटपुट:

• एक बिंदु (sx,sy) 3 subtriangles में त्रिकोण ऐसा है कि प्रत्येक subtriangle बिल्कुल n बिंदु हैं विभाजन कि।

जिस तरह से विभाजित बिंदु बाध्यकारी त्रिभुज को subtriangles में विभाजित करता है, निम्नानुसार है: विभाजन बिंदु से तीन पंक्तियों में से प्रत्येक पंक्ति को एक रेखा बनाएं। यह त्रिकोण को 3 subtriangles में विभाजित करेगा।

हमें गारंटी है कि ऐसा बिंदु मौजूद है। ऐसा कोई भी बिंदु पर्याप्त होगा (उत्तर जरूरी नहीं है)।

n=2 (6 अंक) के लिए समस्या का एक उदाहरण यहां दिया गया है। हमें प्रत्येक रंगीन बिंदुओं के समन्वय और बड़े त्रिकोण के प्रत्येक चरम के निर्देशांक दिए जाते हैं। विभाजन बिंदु ग्रे में घिरा हुआ है।

कोई तेजी से O(n^2) से एक एल्गोरिथ्म का सुझाव कर सकते हैं?

Answer 1

यहां एक O(n log n) एल्गोरिदम है। आइए कोई अपमान नहीं मानते हैं।

उच्च स्तरीय विचार है, एक त्रिकोण PQR दिया,

P 
    C \ 
/S\ 
R-----Q 

हम शुरू में P पर केंद्र बिंदु C जगह। स्लाइड CR की तरफ n त्रिभुज CPQ और 0 (S) सेगमेंट CQ पर बिंदुओं के अंदर n अंक हैं। स्लाइड CQ की तरफ या तो त्रिभुज CRP अब और कमी नहीं है (perturb C और हम कर चुके हैं) या CP एक बिंदु हिट करता है। बाद के मामले में, CP से दूर त्रिकोण CRP अब तक की कमी नहीं है (हम कर चुके हैं) या CQ एक बिंदु हिट करता है, इस स्थिति में हम C को Q पर फिर से स्लाइड करना शुरू करते हैं।

जाहिर कार्यान्वयन नहीं कर सकते हैं "स्लाइड" अंक, C से जुड़े प्रत्येक त्रिकोण, प्रत्येक शिखर कि C से त्रिकोण अन्य की S के लिए के लिए हां, तो एक द्विआधारी खोज वृक्ष S साथ कोण के अनुसार क्रमबद्ध में त्रिकोण के अंदर अंक की दुकान। ये संरचनाएं इस गतिशील एल्गोरिदम को लागू करने के लिए पर्याप्त हैं।

मैं इस सबूत के बिना जोर देता हूं कि यह एल्गोरिदम सही है।

चलने के समय के रूप में, प्रत्येक घटना एक पॉइंट-लाइन चौराहे है और इसे O(log n) में संभाला जा सकता है। कोण PC और QC और RC सभी monotonic हैं, इसलिए O(1) लाइनों में से प्रत्येक एक बार में प्रत्येक बिंदु को हिट करता है।

Answer 2

यहां एक ऐसा दृष्टिकोण है जो ओ (लॉग एन) को प्रत्येक लागत के पास लेता है।

प्रत्येक पास प्रारंभिक बिंदु से शुरू होता है, जो त्रिकोण को वहां subtriangles में विभाजित करता है। यदि प्रत्येक के पास अंक हैं, तो हम समाप्त हो गए हैं। यदि नहीं, तो subtriangle पर विचार करें जो वांछित एन से दूर दूर है। मान लीजिए कि अभी बहुत सारे हैं, अभी के लिए। असंतुलन शून्य पर योग होता है, इसलिए कम से कम दो अन्य subtriangles में से एक बहुत कम अंक है। तीसरे उप-समूह में भी बहुत कम है, या वास्तव में एन अंक हैं - या मूल उप-समूह में उच्चतम विसंगति नहीं होगी।

सबसे असंतुलित सबट्रियांग लें और इससे दूर की ओर लाइन के साथ केंद्र बिंदु को स्थानांतरित करने पर विचार करें। जैसा कि आप ऐसा करते हैं, सबसे असंतुलित बिंदु का असंतुलन कम हो जाएगा। त्रिकोण में प्रत्येक बिंदु के लिए, जब आप केंद्र बिंदु को स्थानांतरित करते हैं तो आप उस बिंदु को सबसे असंतुलित उप-समूह से बाहर या बाहर पार कर सकते हैं। इसलिए आप समय पर काम कर सकते हैं जहां केंद्र बिंदु को स्थानांतरित करने के लिए सबसे असंतुलित त्रिभुज किसी भी वांछित गिनती प्रदान करने के लिए।

जैसे ही आप केंद्र बिंदु को स्थानांतरित करते हैं, आप चुन सकते हैं कि हमारे असंतुलित सबट्रियांगल में से कौन से अंक आगे बढ़ते हैं, लेकिन आप यह नहीं चुन सकते कि वे कौन से दो उप-समूह हैं, या इससे - लेकिन आप भविष्यवाणी कर सकते हैं कि कौन आसानी से लाइन के किनारे से आप केंद्र बिंदु को स्लाइड कर रहे हैं, इसलिए आप इस लाइन के साथ केंद्र बिंदु को स्थानांतरित करने के बाद सबसे कम अधिकतम विसंगति प्राप्त कर सकते हैं। सबसे बुरे मामले में, सभी बिंदुओं को वास्तव में संतुलित किया गया था, जो subtriangle में, या बाहर चला गया। हालांकि, अगर असंतुलित उप-समूह में एन/के अंक होते हैं, तो उनमें से/2 को स्थानांतरित करके, आप सबसे खराब स्थिति में स्थानांतरित कर सकते हैं, जहां यह और पहले संतुलित सबट्रियाल के/2 से बाहर होते हैं। तीसरा उप-समूह अभी भी दूसरी दिशा में के तक असंतुलित हो सकता है, लेकिन इस मामले में दूसरा पास अधिकतम असंतुलन को कम/2 के नीचे कम कर देगा।

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

Answer 3

मुख्य विचार यह है: यदि हमें लाइन मिल गई है, तो हम रैखिक खोज का उपयोग करके उस पर एक बिंदु खोजने का प्रयास कर सकते हैं। यदि रेखा पर्याप्त नहीं है, तो हम इसे बाइनरी खोज का उपयोग करके स्थानांतरित कर सकते हैं।

1. क्रमबद्ध अंक शिखर A से दिशा के आधार पर। उन्हें B और C के लिए भी क्रमबद्ध करें।
2. सभी बिंदुओं के लिए vertex A के लिए वर्तमान सीमा सेट करें।
3. vertex A के लिए सीमा से 2 मध्यम बिंदुओं का चयन करें। ये 2 अंक 'ए' के ​​लिए उप-श्रेणी परिभाषित करते हैं। इन बिंदुओं के बीच कुछ पंक्ति AD प्राप्त करें।
4. B और AD (BA से शुरू) के बीच स्थित सभी बिंदुओं के लिए Iterate। n अंक मिलने पर रोकें। n के बाद n और अगले अंक के लिए B से निर्देश के subrange का चयन करें (यदि वहाँ n के बाद कोई मतलब नहीं है, BC उपयोग करें)। यदि n अंक से कम पाया जा सकता है, तो मौजूदा श्रेणी के बाएं आधे होने के लिए वर्टेक्स A के लिए वर्तमान रेंज सेट करें और चरण 3 पर जाएं।
5. चरण 4 के समान, लेकिन vertex C के लिए।
6. अगर A, B, C छेड़छाड़ करते हैं, तो वहां से कोई भी बिंदु चुनें और समाप्त करें। अन्यथा, अगर A&BA के करीब है, शिखर A वर्तमान सीमा के आधे दाएं भाग होने के लिए और कदम 3. अन्यथा सेट वर्तमान सीमा शिखर A वर्तमान सीमा के बाईं आधा होने के लिए जाने के लिए और कदम जाना के लिए वर्तमान सीमा सेट 3.

जटिलता: छँटाई O(n * log n), खोज O(n * log n)। (बाइनरी और रैखिक खोज का संयोजन)।

Answer 4

मुझे लगता है कि एक रेखीय समय एल्गोरिथ्म है। पेपर के आखिरी पैराग्राफ को देखें "बाढ़ की रोशनी द्वारा रोशनी- स्टीगर और स्ट्रेइनू द्वारा"। उनका एल्गोरिदम किसी भी के 1, के 2, के 3 के लिए काम करता है जो एन तक मिलता है। इसलिए, k1 = k2 = k3 = n/3 एक विशेष मामला है।

यहां वह लिंक है जहां आप लेख पा सकते हैं। http://www.sciencedirect.com/science/article/pii/S0925772197000278 एक साइटसेरएक्स लिंक http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.4634