बहुभुज विभाजन

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

बहुभुज विभाजन कम्प्यूटेशनल ज्यामिति में समस्याओं का एक महत्वपूर्ण वर्ग है। कई अलग-अलग बहुभुज विभाजन समस्याएं हैं, विभाजन किए जा रहे बहुभुज के प्रकार और विभाजन में अनुमत इकाइयों के प्रकार पर निर्भर करता है।

पॉलीगॉन अपघटन शब्द का प्रयोग अक्सर एक सामान्य शब्द के रूप में किया जाता है जिसमें बहुभुज आवरण और विभाजन दोनों शामिल होते हैं।

अनुप्रयोग

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

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

एक बहुभुज को त्रिभुजों में विभाजित करना

Main articles: Polygon triangulation and Minimum-weight triangulation

सबसे अच्छी तरह से अध्ययन की गई बहुभुज विभाजन समस्या त्रिकोणों की एक छोटी संख्या में विभाजन है, जिसे बहुभुज त्रिकोणासन भी कहा जाता है। एक छेद-मुक्त बहुभुज के साथ $n$ कोने, एक त्रिभुज की गणना समय में की जा सकती है $\Theta (n)$. छेद वाले बहुभुज के लिए, निम्न सीमा होती है $\Omega (n\log n)$.

एक संबंधित समस्या न्यूनतम कुल किनारे की लंबाई वाले त्रिकोणों में विभाजन कर रही है, जिसे न्यूनतम-भार त्रिकोणासन भी कहा जाता है।

एक बहुभुज को छद्म-त्रिकोणों में विभाजित करना

Main article: Pseudotriangle § Pseudotriangulations

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

[[आयताकार बहुभुज]] को आयतों में विभाजित करना

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

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

घटकों की संख्या को कम करना

घटक आयतों की संख्या को कम करने की समस्या बहुपद है: कई बहुपद-समय एल्गोरिदम ज्ञात हैं। देखना और सर्वेक्षण के लिए।

एक सीधीरेखीय बहुभुज को वर्गों की सबसे छोटी संख्या (मनमाने आयतों के विपरीत) में विभाजित करने की समस्या एनपी-कठिन है।

कुल किनारे की लंबाई को कम करना

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

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

यदि कच्चे बहुभुज में छेद हो सकते हैं, भले ही वे पतित छेद (यानी, एकल बिंदु) हों, तो समस्या एनपी-हार्ड है। इसे प्लानर सैट से घटाकर साबित किया जा सकता है। उस मामले के लिए जिसमें सभी छेद एकल बिंदु हैं, कई स्थिर-कारक सन्निकटन विकसित किए गए हैं:

• ए (3+sqrt(3)) समय में सन्निकटन $O(n^{2})$;*A (3+sqrt(3)) समय में सन्निकटन $O(n\log {n})$;
• समय में एक 4 सन्निकटन $O(n\log {n})$ (अधिक सामान्यतः, डी आयामों में, यह एक है $2d$ समय में सन्निकटन $O(dn\log {n})$),
• समय में 3 सन्निकटन $O(n^{4})$;
• समय में 1.75 सन्निकटन $O(n^{5})$ (अधिक सामान्यतः, डी आयामों में, यह एक है $2d-4+4/d$ समय में सन्निकटन $O(dn^{2d+1})$); बाद वाला सन्निकटन गिलोटिन विभाजन नामक समस्या के एक प्रतिबंधित संस्करण का उपयोग करता है, जिसमें कट गिलोटिन कट (एज-टू-एज कट) होने चाहिए।
• परिष्कृत गिलोटिन कटौती का उपयोग करते हुए कई बहुपद-समय सन्निकटन योजनाएं।

रिक्त स्थान की संख्या कम करना

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

• यदि बड़ा बहुभुज एक आयत है, तो n आयतों की किसी भी अधिकतम व्यवस्था में, सभी छेद आयत होते हैं, और उनकी संख्या अधिक से अधिक होती है $n-\lceil 2{\sqrt {n}}-1\rceil$, और यह तंग है।
• यदि बड़ा बहुभुज T प्रतिवर्ती शीर्षों वाला एक सरलरेखीय बहुभुज है, तो n आयतों की किसी भी अधिकतम व्यवस्था में, छिद्रों को अधिक से अधिक विभाजित किया जा सकता है $T+n-\lceil 2{\sqrt {n}}-1\rceil$ आयताकार, और यह तंग है।

एक बहुभुज को चतुर्भुज में विभाजित करें

वीएलएसआई आर्टवर्क प्रोसेसिंग सिस्टम में, बहुधा एक बहुभुज क्षेत्र को दो क्षैतिज पक्षों के साथ ट्रैपेज़ोइड्स की न्यूनतम संख्या में विभाजित करने की आवश्यकता होती है। एक क्षैतिज भुजा वाले त्रिभुज को दो क्षैतिज भुजाओं वाला एक समलम्बाकार माना जाता है, जिनमें से एक पतित है। एक छेद-मुक्त बहुभुज के साथ $n$ पक्षों, समय में सबसे छोटा ऐसा विभाजन पाया जा सकता है $O(n^{2})$.

यदि ट्रेपेज़ोइड्स की संख्या कम से कम नहीं होनी चाहिए, तो समय पर ट्रैपेज़ॉइडेशन पाया जा सकता है $O(n)$, बहुभुज त्रिभुज एल्गोरिथम के उप-उत्पाद के रूप में। यदि बहुभुज में छेद होते हैं, तो समस्या एनपी-पूर्ण है, लेकिन समय में 3-सन्निकटन पाया जा सकता है $O(n\log n)$.

एक बहुभुज को उत्तल चतुर्भुजों में विभाजित करें

एक चतुर्भुज या चतुष्कोण चतुर्भुज में एक विभाजन है।

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

स्टेनर बिंदुओं के साथ छेद-मुक्त बहुभुजों के चतुष्कोणों के लिए रैखिक-समय एल्गोरिदम हैं, लेकिन उन्हें सबसे छोटा विभाजन खोजने की गारंटी नहीं है।

== एक बहुभुज को m-gons == में विभाजित करें पिछली समस्याओं का एक सामान्यीकरण उन बहुभुजों में विभाजन है जिनकी ठीक m भुजाएँ हैं, या अधिकतम m भुजाएँ हैं। यहाँ लक्ष्य कुल किनारे की लंबाई को कम करना है। इस समस्या को n और m में समय बहुपद में हल किया जा सकता है।

एक बहुभुज को उत्तल बहुभुजों में विभाजित करें

उत्तल बहुभुजों में एक सामान्य बहुभुज का विभाजन करते समय, कई उद्देश्यों का अध्ययन किया गया है।

घटकों की संख्या को कम करना

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

रिक्त स्थान की संख्या कम करना

मूल बहुभुज में पहले से ही कुछ जोड़ीदार-असंबद्ध उत्तल आकृतियाँ हैं, और लक्ष्य इसे उत्तल बहुभुजों में विभाजित करना है, ताकि प्रत्येक मूल आकृति टुकड़ों में से एक में समाहित हो, और इसके अधीन, रिक्त स्थानों की संख्या (टुकड़े जो नहीं एक मूल आंकड़ा शामिल करें) जितना संभव हो उतना छोटा है। यदि बड़ा बहुभुज उत्तल है, तो n उत्तल आकृतियों की किसी भी अधिकतम व्यवस्था में, सभी छेद उत्तल होते हैं, और उनकी संख्या अधिक से अधिक होती है $2$