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

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

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

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

अनुप्रयोग

बहुभुज अपघटन कई क्षेत्रों में लागू होता है:

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

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

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

Main articles: बहुभुज त्रिभुज and न्यूनतम वजन त्रिकोण

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

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

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

Main article: छद्मत्रिभुज § स्यूडोट्राएंगुलेशन

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

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

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

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

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

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

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

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

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

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

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

• A (3+sqrt(3)) समय में सन्निकटन $O(n^{2})$;
• A (3+sqrt(3)) समय में सन्निकटन $O(n\log {n})$;
• समय में 4 सन्निकटन $O(n\log {n})$ (अधिक सामान्यतः, d आयामों में, यह एक है $2d$ समय में सन्निकटन $O(dn\log {n})$),
• समय में 3 सन्निकटन $O(n^{4})$;
• समय में 1.75 सन्निकटन $O(n^{5})$ (अधिक सामान्यतः, d आयामों में, यह एक होती है $2$