बहुभुज विभाजन: Difference between revisions

Revision as of 10:16, 19 May 2023

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

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

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

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

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

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

घटकों के आयतों की संख्या को कम करने की समस्या बहुपद होती है: कई बहुपद समय ऐल्‍गोरिथ्‍म ज्ञात हैं। देखो ^[1]^: 10–13 और ^[2]^: 3–5 सर्वेक्षण के लिए होता है।

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

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

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

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

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

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

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

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

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

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

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

यदि समलम्बाभ की संख्या कम से कम नहीं होनी चाहिए, तो समय पर समलम्बाकार पाया जा सकता है $O (n$

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

@@ Line 75: / Line 75: @@
 इष्टतम उत्तल विभाजन समस्या एक गैर-[[उत्तल बहुभुज]] को यथासंभव कुछ उत्तल बहुभुजों में विभाजित करता  है, केवल प्रारंभिक बहुभुज के कोने का उपयोग करना। इस समस्या के लिए सटीक और अनुमानित एल्गोरिदम हैं।<ref>{{Cite journal|last1=Hertel|first1=Stefan|last2=Mehlhorn|first2=Kurt|date=1983|editor-last=Karpinski|editor-first=Marek|title=सरल बहुभुजों का तीव्र त्रिभुजन|url=https://link.springer.com/chapter/10.1007/3-540-12689-9_105|journal=Foundations of Computation Theory|series=Lecture Notes in Computer Science|volume=158|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=207–218|doi=10.1007/3-540-12689-9_105|isbn=978-3-540-38682-7}}</ref>
 === रिक्त स्थान की संख्या कम करना ===
-मूल बहुभुज में पहले से ही कुछ  युग्‍मानूसार-असंबद्ध उत्तल आकृतियाँ होती हैं, और उद्देश्य से इसे उत्तल बहुभुजों में विभाजित करना होता है, अर्थात प्रत्येक मूल आकृति खण्ड़ो  में से एक में समाहित हो, और इसके अधीन, रिक्त स्थानों की संख्या (टुकड़े जो नहीं एक मूल आंकड़ा सम्मलित करें) जितना संभव हो उतना छोटा होता है। यदि बड़ा बहुभुज उत्तल है, तो n उत्तल आकृतियों की किसी भी अधिकतम क्रम बद्धता में, सभी छिद्र उत्तल होते हैं, और उनकी संख्या अधिक से अधिक होती है <math>2n-5</math>, और यह संक्षेप होता है।<ref name=":4" />
+मूल बहुभुज में पहले से ही कुछ  युग्‍मानूसार-असंबद्ध उत्तल आकृतियाँ होती हैं, और उद्देश्य से इसे उत्तल बहुभुजों में विभाजित करना होता है, अर्थात प्रत्येक मूल आकृति खण्ड़ो  में से एक में समाहित हो, और इसके अधीन, रिक्त स्थानों की संख्या (टुकड़े जो नहीं एक मूल आंकड़ा सम्मलित करें) जितना संभव हो उतना छोटा होता है। यदि बड़ा बहुभुज उत्तल है, तो n उत्तल आकृतियों की किसी भी अधिकतम क्रम बद्धता में, सभी छिद्र उत्तल होते हैं, और उनकी संख्या अधिक से अधिक होती है <math>2n-5</math>, और यह घन होता है।<ref name=":4" />
 === क्षेत्र और परिधि को बराबर करना ===
 निष्पक्ष बहुभुज विभाजन समस्या <ref>{{Cite journal|last1=Nandakumar|first1=R.|last2=Rao|first2=N. Ramana|date=August 2012|title=बहुभुजों का 'मेला' विभाजन - एक परिचय|url=http://arxiv.org/abs/0812.2241|journal=Proceedings - Mathematical Sciences|volume=122|issue=3|pages=459–467|arxiv=0812.2241|doi=10.1007/s12044-012-0076-5|issn=0253-4142|s2cid=189909962}}</ref> एक ''(उत्तल)'' ''बहुभुज'' को एक समान परिधि और समान क्षेत्रो के साथ (उत्तल) खण्ड़ो में विभाजित करना है (यह निष्पक्ष केक  काटने का एक विशेष स्थिति होती है)। किसी भी उत्तल बहुभुज को ठीक 1/n के क्षेत्र वाले उत्तल स्थान के किसी भी संख्या ''n'' मे आसानी से काटा जा सकता है। चूंकि , यह सुनिश्चित करना कि खण्ड़ो का क्षेत्रफल बराबर हो और परिमाप समान हो, इसे अधिक चुनौतीपूर्ण बनाता है। इस समस्या को हल करने के लिए एल्गोरिदम हैं जब खण्ड़ो की संख्या 2 की शक्ति होती है।<ref>{{Cite journal|last1=Armaselu|first1=Bogdan|last2=Daescu|first2=Ovidiu|date=2015-11-23|title=उत्तल बहुभुजों के निष्पक्ष विभाजन के लिए एल्गोरिदम|journal=Theoretical Computer Science|language=en|volume=607|pages=351–362|doi=10.1016/j.tcs.2015.08.003|issn=0304-3975|doi-access=free}}</ref>

Anonymous

Search