बहुभुज विभाजन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Set of basic shapes which assemble into a polygon}} | {{Short description|Set of basic shapes which assemble into a polygon}} | ||
[[ज्यामिति]] में, [[बहुभुज]] का एक विभाजन अभाज्य इकाइयों (जैसे वर्ग) का एक समूह है, जो अतिव्याप्त नहीं होता है और जिसका [[संघ (सेट सिद्धांत)]] | [[ज्यामिति]] में, [[बहुभुज]] का एक विभाजन अभाज्य इकाइयों (जैसे वर्ग) का एक समूह है, जो अतिव्याप्त नहीं होता है और जिसका [[संघ (सेट सिद्धांत)|मिलन बहुभुज]] के बराबर होता है। एक बहुभुज विभाजन समस्या एक ऐसे विभाजन को खोजने की समस्या है जो किसी अर्थ में न्यूनतम है, उदाहरण के लिए इकाइयों की सबसे छोटी संख्या या सबसे छोटी कुल पार्श्व-लंबाई वाली इकाइयों वाला विभाजन होता है । | ||
बहुभुज विभाजन [[कम्प्यूटेशनल ज्यामिति]] में समस्याओं का एक महत्वपूर्ण वर्ग है। | बहुभुज विभाजन [[कम्प्यूटेशनल ज्यामिति]] में समस्याओं का एक महत्वपूर्ण वर्ग होता है। विभाजन किए जा रहे बहुभुज के प्रकार और विभाजन में अनुमत इकाइयों के प्रकार के आधार पर, कई अलग-अलग बहुभुज विभाजन समस्याएँ होती हैं। | ||
पॉलीगॉन अपघटन शब्द का प्रयोग | पॉलीगॉन अपघटन शब्द का प्रयोग अधिकांशतः एक सामान्य शब्द के रूप में किया जाता है जिसमें [[बहुभुज आवरण]] और विभाजन दोनों सम्मलित होते हैं।<ref name=Keil2000>{{Cite book|doi=10.1016/B978-044482537-7/50012-7|chapter=Polygon Decomposition|title=कम्प्यूटेशनल ज्यामिति की पुस्तिका|pages=491–518|year=2000|last1=Mark Keil|first1=J.|isbn=9780444825377}}</ref> | ||
| Line 11: | Line 11: | ||
बहुभुज अपघटन कई क्षेत्रों में लागू होता है:<ref name=Keil2000/>* पैटर्न पहचान तकनीक किसी वस्तु का वर्णन, पहचान या वर्गीकरण करने के लिए उससे जानकारी निकालती है। एक सामान्य बहुभुज वस्तु को पहचानने के लिए एक स्थापित रणनीति यह है कि इसे सरल घटकों में विघटित किया जाए, फिर घटकों और उनके अंतर्संबंधों की पहचान की जाए और इस जानकारी का उपयोग वस्तु के आकार को निर्धारित करने के लिए किया जाए। | बहुभुज अपघटन कई क्षेत्रों में लागू होता है:<ref name=Keil2000/>* पैटर्न पहचान तकनीक किसी वस्तु का वर्णन, पहचान या वर्गीकरण करने के लिए उससे जानकारी निकालती है। एक सामान्य बहुभुज वस्तु को पहचानने के लिए एक स्थापित रणनीति यह है कि इसे सरल घटकों में विघटित किया जाए, फिर घटकों और उनके अंतर्संबंधों की पहचान की जाए और इस जानकारी का उपयोग वस्तु के आकार को निर्धारित करने के लिए किया जाए। | ||
* [[वीएलएसआई]] कलाकृति डाटा प्रोसेसिंग में, लेआउट को बहुभुज के रूप में दर्शाया जाता है, और इलेक्ट्रॉन-बीम लिथोग्राफी की तैयारी के लिए एक दृष्टिकोण इन बहुभुज क्षेत्रों को मौलिक आंकड़ों में विघटित करना है। रूटिंग क्षेत्र को चैनलों में विभाजित करने की प्रक्रिया में बहुभुज अपघटन का भी उपयोग किया जाता है। | * [[वीएलएसआई]] कलाकृति डाटा प्रोसेसिंग में, लेआउट को बहुभुज के रूप में दर्शाया जाता है, और इलेक्ट्रॉन-बीम लिथोग्राफी की तैयारी के लिए एक दृष्टिकोण इन बहुभुज क्षेत्रों को मौलिक आंकड़ों में विघटित करना है। रूटिंग क्षेत्र को चैनलों में विभाजित करने की प्रक्रिया में बहुभुज अपघटन का भी उपयोग किया जाता है। | ||
* कम्प्यूटेशनल ज्यामिति में, सामान्य बहुभुजों पर समस्याओं के लिए एल्गोरिदम | * कम्प्यूटेशनल ज्यामिति में, सामान्य बहुभुजों पर समस्याओं के लिए एल्गोरिदम अधिकांशतः उत्तल या स्टार-आकार जैसे प्रतिबंधित प्रकार के बहुभुजों की तुलना में अधिक जटिल होते हैं। पॉलीगॉन में पॉइंट | पॉइंट-इन-पॉलीगॉन समस्या इसका एक उदाहरण है। सामान्य बहुभुजों पर इस प्रकार की कुछ समस्याओं को हल करने की एक रणनीति है कि बहुभुज को सरल घटक भागों में विघटित किया जाए, एक विशेष एल्गोरिथम का उपयोग करके प्रत्येक घटक पर समस्या को हल किया जाए, और फिर आंशिक समाधानों को संयोजित किया जाए। | ||
* अन्य अनुप्रयोगों में [[आधार - सामग्री संकोचन]], [[डेटाबेस सिस्टम]], [[ मूर्ति प्रोद्योगिकी ]] और [[ कंप्यूटर चित्रलेख ]] | * अन्य अनुप्रयोगों में [[आधार - सामग्री संकोचन]], [[डेटाबेस सिस्टम]], [[ मूर्ति प्रोद्योगिकी ]] और [[ कंप्यूटर चित्रलेख ]] सम्मलित हैं। | ||
== एक बहुभुज को त्रिभुजों में विभाजित करना == | == एक बहुभुज को त्रिभुजों में विभाजित करना == | ||
| Line 51: | Line 51: | ||
=== रिक्त स्थान की संख्या कम करना === | === रिक्त स्थान की संख्या कम करना === | ||
इस सेटिंग में, बड़े बहुभुज में पहले से ही कुछ जोड़ीदार-असंबद्ध आयत | इस सेटिंग में, बड़े बहुभुज में पहले से ही कुछ जोड़ीदार-असंबद्ध आयत सम्मलित हैं। लक्ष्य बहुभुज के विभाजन को आयतों में इस तरह खोजना है कि प्रत्येक मूल आयत टुकड़ों में से एक में समाहित हो, और इसके अधीन, रिक्त स्थानों की संख्या (टुकड़े जिनमें मूल आयत नहीं है) जितना संभव हो उतना छोटा है। निम्नलिखित परिणाम ज्ञात हैं:<ref name=":4">{{Cite journal|last1=Akopyan|first1=Arseniy|last2=Segal-Halevi|first2=Erel|date=2018-01-01|title=बहुभुज व्यवस्था में रिक्त स्थान की गणना|url=https://epubs.siam.org/doi/abs/10.1137/16M110407X|journal=SIAM Journal on Discrete Mathematics|volume=32|issue=3|pages=2242–2257|doi=10.1137/16M110407X|issn=0895-4801|arxiv=1604.00960|s2cid=123397485 }}</ref> | ||
* यदि बड़ा बहुभुज एक आयत है, तो n आयतों की किसी भी अधिकतम व्यवस्था में, सभी छेद आयत होते हैं, और उनकी संख्या अधिक से अधिक होती है <math>n - \lceil 2 \sqrt{n} - 1\rceil</math>, और यह तंग है। | * यदि बड़ा बहुभुज एक आयत है, तो n आयतों की किसी भी अधिकतम व्यवस्था में, सभी छेद आयत होते हैं, और उनकी संख्या अधिक से अधिक होती है <math>n - \lceil 2 \sqrt{n} - 1\rceil</math>, और यह तंग है। | ||
* यदि बड़ा बहुभुज T प्रतिवर्ती शीर्षों वाला एक सरलरेखीय बहुभुज है, तो n आयतों की किसी भी अधिकतम व्यवस्था में, छिद्रों को अधिक से अधिक विभाजित किया जा सकता है <math>T + n - \lceil 2 \sqrt{n} - 1\rceil</math> आयताकार, और यह तंग है। | * यदि बड़ा बहुभुज T प्रतिवर्ती शीर्षों वाला एक सरलरेखीय बहुभुज है, तो n आयतों की किसी भी अधिकतम व्यवस्था में, छिद्रों को अधिक से अधिक विभाजित किया जा सकता है <math>T + n - \lceil 2 \sqrt{n} - 1\rceil</math> आयताकार, और यह तंग है। | ||
| Line 82: | Line 82: | ||
=== रिक्त स्थान की संख्या कम करना === | === रिक्त स्थान की संख्या कम करना === | ||
मूल बहुभुज में पहले से ही कुछ जोड़ीदार-असंबद्ध उत्तल आकृतियाँ हैं, और लक्ष्य इसे उत्तल बहुभुजों में विभाजित करना है, ताकि प्रत्येक मूल आकृति टुकड़ों में से एक में समाहित हो, और इसके अधीन, रिक्त स्थानों की संख्या (टुकड़े जो नहीं एक मूल आंकड़ा | मूल बहुभुज में पहले से ही कुछ जोड़ीदार-असंबद्ध उत्तल आकृतियाँ हैं, और लक्ष्य इसे उत्तल बहुभुजों में विभाजित करना है, ताकि प्रत्येक मूल आकृति टुकड़ों में से एक में समाहित हो, और इसके अधीन, रिक्त स्थानों की संख्या (टुकड़े जो नहीं एक मूल आंकड़ा सम्मलित करें) जितना संभव हो उतना छोटा है। यदि बड़ा बहुभुज उत्तल है, तो n उत्तल आकृतियों की किसी भी अधिकतम व्यवस्था में, सभी छेद उत्तल होते हैं, और उनकी संख्या अधिक से अधिक होती है <math>2n-5</math>, और यह तंग है।<ref name=":4" /> | ||
| Line 91: | Line 91: | ||
== अधिक सामान्य घटक आकार == | == अधिक सामान्य घटक आकार == | ||
टुकड़ों के अधिक सामान्य आकार का अध्ययन किया गया है, जिनमें | टुकड़ों के अधिक सामान्य आकार का अध्ययन किया गया है, जिनमें सम्मलित हैं: सर्पिल आकार, स्टार बहुभुज और [[मोनोटोन बहुभुज]]। देखना <ref name="Keil2000" />एक सर्वेक्षण के लिए। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 01:46, 17 May 2023
ज्यामिति में, बहुभुज का एक विभाजन अभाज्य इकाइयों (जैसे वर्ग) का एक समूह है, जो अतिव्याप्त नहीं होता है और जिसका मिलन बहुभुज के बराबर होता है। एक बहुभुज विभाजन समस्या एक ऐसे विभाजन को खोजने की समस्या है जो किसी अर्थ में न्यूनतम है, उदाहरण के लिए इकाइयों की सबसे छोटी संख्या या सबसे छोटी कुल पार्श्व-लंबाई वाली इकाइयों वाला विभाजन होता है ।
बहुभुज विभाजन कम्प्यूटेशनल ज्यामिति में समस्याओं का एक महत्वपूर्ण वर्ग होता है। विभाजन किए जा रहे बहुभुज के प्रकार और विभाजन में अनुमत इकाइयों के प्रकार के आधार पर, कई अलग-अलग बहुभुज विभाजन समस्याएँ होती हैं।
पॉलीगॉन अपघटन शब्द का प्रयोग अधिकांशतः एक सामान्य शब्द के रूप में किया जाता है जिसमें बहुभुज आवरण और विभाजन दोनों सम्मलित होते हैं।[1]
अनुप्रयोग
बहुभुज अपघटन कई क्षेत्रों में लागू होता है:[1]* पैटर्न पहचान तकनीक किसी वस्तु का वर्णन, पहचान या वर्गीकरण करने के लिए उससे जानकारी निकालती है। एक सामान्य बहुभुज वस्तु को पहचानने के लिए एक स्थापित रणनीति यह है कि इसे सरल घटकों में विघटित किया जाए, फिर घटकों और उनके अंतर्संबंधों की पहचान की जाए और इस जानकारी का उपयोग वस्तु के आकार को निर्धारित करने के लिए किया जाए।
- वीएलएसआई कलाकृति डाटा प्रोसेसिंग में, लेआउट को बहुभुज के रूप में दर्शाया जाता है, और इलेक्ट्रॉन-बीम लिथोग्राफी की तैयारी के लिए एक दृष्टिकोण इन बहुभुज क्षेत्रों को मौलिक आंकड़ों में विघटित करना है। रूटिंग क्षेत्र को चैनलों में विभाजित करने की प्रक्रिया में बहुभुज अपघटन का भी उपयोग किया जाता है।
- कम्प्यूटेशनल ज्यामिति में, सामान्य बहुभुजों पर समस्याओं के लिए एल्गोरिदम अधिकांशतः उत्तल या स्टार-आकार जैसे प्रतिबंधित प्रकार के बहुभुजों की तुलना में अधिक जटिल होते हैं। पॉलीगॉन में पॉइंट | पॉइंट-इन-पॉलीगॉन समस्या इसका एक उदाहरण है। सामान्य बहुभुजों पर इस प्रकार की कुछ समस्याओं को हल करने की एक रणनीति है कि बहुभुज को सरल घटक भागों में विघटित किया जाए, एक विशेष एल्गोरिथम का उपयोग करके प्रत्येक घटक पर समस्या को हल किया जाए, और फिर आंशिक समाधानों को संयोजित किया जाए।
- अन्य अनुप्रयोगों में आधार - सामग्री संकोचन, डेटाबेस सिस्टम, मूर्ति प्रोद्योगिकी और कंप्यूटर चित्रलेख सम्मलित हैं।
एक बहुभुज को त्रिभुजों में विभाजित करना
सबसे अच्छी तरह से अध्ययन की गई बहुभुज विभाजन समस्या त्रिकोणों की एक छोटी संख्या में विभाजन है, जिसे बहुभुज त्रिकोणासन भी कहा जाता है। एक छेद-मुक्त बहुभुज के साथ कोने, एक त्रिभुज की गणना समय में की जा सकती है . छेद वाले बहुभुज के लिए, निम्न सीमा होती है .
एक संबंधित समस्या न्यूनतम कुल किनारे की लंबाई वाले त्रिकोणों में विभाजन कर रही है, जिसे न्यूनतम-भार त्रिकोणासन भी कहा जाता है।
एक बहुभुज को छद्म-त्रिकोणों में विभाजित करना
समस्या के समान दो रूपों का अध्ययन उस मामले के लिए किया गया था जिसमें टुकड़े छद्म त्रिभुज होने चाहिए - बहुभुज जो त्रिभुजों की तरह तीन उत्तल शिखर होते हैं। वेरिएंट हैं: सबसे छोटी संख्या में छद्मत्रिभुजों का विभाजन, और न्यूनतम कुल किनारे की लंबाई के साथ छद्मत्रिकोणों का विभाजन।
[[आयताकार बहुभुज]] को आयतों में विभाजित करना
बहुभुज विभाजन समस्याओं का एक विशेष उप-परिवार तब उत्पन्न होता है जब बड़ा बहुभुज एक सरलरेखीय बहुभुज होता है (जिसे: ओर्थोगोनल बहुभुज भी कहा जाता है)। इस मामले में, विचार करने के लिए सबसे महत्वपूर्ण घटक आकार आयत है।[1]
आयताकार विभाजन में कई अनुप्रयोग होते हैं। वीएलएसआई डिजाइन में, लिथोग्राफिक पैटर्न जनरेटर में उपलब्ध सरल आकृतियों में मास्क को विघटित करना आवश्यक है, और इसी तरह की मुखौटा अपघटन की समस्या डीएनए माइक्रोएरे डिजाइन में भी उत्पन्न होती है। आयताकार विभाजन इमेज प्रोसेसिंग में कनवल्शन ऑपरेशंस को आसान बना सकते हैं और बिटमैप चित्र को कंप्रेस करने के लिए इस्तेमाल किया जा सकता है। बारीकी से संबंधित मैट्रिक्स अपघटन की समस्याओं को विकिरण चिकित्सा योजना पर लागू किया गया है, और रोबोट स्व-विधानसभा अनुक्रमों को डिजाइन करने के लिए आयताकार विभाजन का भी उपयोग किया गया है।[2]
घटकों की संख्या को कम करना
घटक आयतों की संख्या को कम करने की समस्या बहुपद है: कई बहुपद-समय एल्गोरिदम ज्ञात हैं। देखना [1]: 10–13 और [2]: 3–5 सर्वेक्षण के लिए।
एक सीधीरेखीय बहुभुज को वर्गों की सबसे छोटी संख्या (मनमाने आयतों के विपरीत) में विभाजित करने की समस्या एनपी-कठिन है।[3]
कुल किनारे की लंबाई को कम करना
कुछ अनुप्रयोगों में, कटौती की कुल लंबाई को कम करना अधिक महत्वपूर्ण है (उदाहरण के लिए विभाजन करने की लागत को कम करने के लिए, या धूल की मात्रा को कम करने के लिए)। इस समस्या को न्यूनतम किनारे-लंबाई का आयताकार विभाजन कहा जाता है। लिंगस, पिंटर, रिवेस्ट और शमीर ने पहली बार 1982 में इसका अध्ययन किया था।[4][5] इस समस्या की रन-टाइम जटिलता महत्वपूर्ण रूप से इस बात पर निर्भर करती है कि कच्चे बहुभुज में छेद होने की अनुमति है या नहीं।
यदि कच्चा बहुभुज छेद रहित है, तो समय पर एक इष्टतम विभाजन पाया जा सकता है , जहाँ n बहुभुज के शीर्षों की संख्या है। हिस्टोग्राम बहुभुज के विशेष मामले में, जटिलता में सुधार होता है .[4]एल्गोरिथ्म गतिशील प्रोग्रामिंग का उपयोग करता है और निम्नलिखित तथ्य पर निर्भर करता है: यदि बहुभुज छेद-मुक्त है, तो इसमें एक न्यूनतम-लंबाई वाला विभाजन होता है जिसमें प्रत्येक अधिकतम रेखा-खंड में सीमा का एक शीर्ष होता है। इसका कारण यह है कि, किसी भी न्यूनतम-लंबाई वाले विभाजन में, प्रत्येक अधिकतम रेखा-खंड को तब तक धकेला जा सकता है, जब तक कि यह कुल लंबाई को बदले बिना सीमा के किसी एक कोने से टकराता है। इसलिए केवल हैं एक इष्टतम विभाजन में एक लाइन खंड के लिए उम्मीदवार, और उन्हें गतिशील प्रोग्रामिंग का उपयोग करके कुशलता से जांचा जा सकता है।[5]: 166–167
यदि कच्चे बहुभुज में छेद हो सकते हैं, भले ही वे पतित छेद (यानी, एकल बिंदु) हों, तो समस्या एनपी-हार्ड है। इसे प्लानर सैट से घटाकर साबित किया जा सकता है।[4][6] उस मामले के लिए जिसमें सभी छेद एकल बिंदु हैं, कई स्थिर-कारक सन्निकटन विकसित किए गए हैं:
- ए (3+sqrt(3)) समय में सन्निकटन ;[6]*A (3+sqrt(3)) समय में सन्निकटन ;[7]
- समय में एक 4 सन्निकटन (अधिक सामान्यतः, डी आयामों में, यह एक है समय में सन्निकटन ),[8]
- समय में 3 सन्निकटन ;
- समय में 1.75 सन्निकटन (अधिक सामान्यतः, डी आयामों में, यह एक है समय में सन्निकटन );[9] बाद वाला सन्निकटन गिलोटिन विभाजन नामक समस्या के एक प्रतिबंधित संस्करण का उपयोग करता है, जिसमें कट गिलोटिन कट (एज-टू-एज कट) होने चाहिए।
- परिष्कृत गिलोटिन कटौती का उपयोग करते हुए कई बहुपद-समय सन्निकटन योजनाएं।[10][11][5]