बहुभुज विभाजन: 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]
रिक्त स्थान की संख्या कम करना
इस सेटिंग में, बड़े बहुभुज में पहले से ही कुछ जोड़ीदार-असंबद्ध आयत सम्मलित हैं। लक्ष्य बहुभुज के विभाजन को आयतों में इस तरह खोजना है कि प्रत्येक मूल आयत टुकड़ों में से एक में समाहित हो, और इसके अधीन, रिक्त स्थानों की संख्या (टुकड़े जिनमें मूल आयत नहीं है) जितना संभव हो उतना छोटा है। निम्नलिखित परिणाम ज्ञात हैं:[12]
- यदि बड़ा बहुभुज एक आयत है, तो n आयतों की किसी भी अधिकतम व्यवस्था में, सभी छेद आयत होते हैं, और उनकी संख्या अधिक से अधिक होती है , और यह तंग है।
- यदि बड़ा बहुभुज T प्रतिवर्ती शीर्षों वाला एक सरलरेखीय बहुभुज है, तो n आयतों की किसी भी अधिकतम व्यवस्था में, छिद्रों को अधिक से अधिक विभाजित किया जा सकता है आयताकार, और यह तंग है।
एक बहुभुज को चतुर्भुज में विभाजित करें
वीएलएसआई आर्टवर्क प्रोसेसिंग सिस्टम में, बहुधा एक बहुभुज क्षेत्र को दो क्षैतिज पक्षों के साथ ट्रैपेज़ोइड्स की न्यूनतम संख्या में विभाजित करने की आवश्यकता होती है। एक क्षैतिज भुजा वाले त्रिभुज को दो क्षैतिज भुजाओं वाला एक समलम्बाकार माना जाता है, जिनमें से एक पतित है। एक छेद-मुक्त बहुभुज के साथ पक्षों, समय में सबसे छोटा ऐसा विभाजन पाया जा सकता है .[13]
यदि ट्रेपेज़ोइड्स की संख्या कम से कम नहीं होनी चाहिए, तो समय पर ट्रैपेज़ॉइडेशन पाया जा सकता है , बहुभुज त्रिभुज एल्गोरिथम के उप-उत्पाद के रूप में।[14] यदि बहुभुज में छेद होते हैं, तो समस्या एनपी-पूर्ण है, लेकिन समय में 3-सन्निकटन पाया जा सकता है .[13]
एक बहुभुज को उत्तल चतुर्भुजों में विभाजित करें
एक चतुर्भुज या चतुष्कोण चतुर्भुज में एक विभाजन है।
चतुष्कोणीय समस्याओं की एक आवर्ती विशेषता यह है कि क्या वे स्टेनर बिंदु (कम्प्यूटेशनल ज्यामिति) की अनुमति है, यानी, क्या एल्गोरिदम को उन बिंदुओं को जोड़ने की अनुमति है जो बहुभुज के कोने नहीं हैं। स्टाइनर पॉइंट्स को अनुमति देने से छोटे डिवीजनों को सक्षम किया जा सकता है, लेकिन फिर यह गारंटी देना अधिक कठिन है कि एल्गोरिदम द्वारा पाए गए डिवीजनों का न्यूनतम आकार है।
स्टेनर बिंदुओं के साथ छेद-मुक्त बहुभुजों के चतुष्कोणों के लिए रैखिक-समय एल्गोरिदम हैं, लेकिन उन्हें सबसे छोटा विभाजन खोजने की गारंटी नहीं है।[15][16]
== एक बहुभुज को m-gons == में विभाजित करें
पिछली समस्याओं का एक सामान्यीकरण उन बहुभुजों में विभाजन है जिनकी ठीक m भुजाएँ हैं, या अधिकतम m भुजाएँ हैं। यहाँ लक्ष्य कुल किनारे की लंबाई को कम करना है। इस समस्या को n और m में समय बहुपद में हल किया जा सकता है।[17][18]
एक बहुभुज को उत्तल बहुभुजों में विभाजित करें
उत्तल बहुभुजों में एक सामान्य बहुभुज का विभाजन करते समय, कई उद्देश्यों का अध्ययन किया गया है।
घटकों की संख्या को कम करना
इष्टतम उत्तल विभाजन समस्या एक गैर-उत्तल बहुभुज को यथासंभव कुछ उत्तल बहुभुजों में विभाजित करना है, केवल प्रारंभिक बहुभुज के कोने का उपयोग करना। इस समस्या के लिए सटीक और अनुमानित एल्गोरिदम हैं।[19]
रिक्त स्थान की संख्या कम करना
मूल बहुभुज में पहले से ही कुछ जोड़ीदार-असंबद्ध उत्तल आकृतियाँ हैं, और लक्ष्य इसे उत्तल बहुभुजों में विभाजित करना है, ताकि प्रत्येक मूल आकृति टुकड़ों में से एक में समाहित हो, और इसके अधीन, रिक्त स्थानों की संख्या (टुकड़े जो नहीं एक मूल आंकड़ा सम्मलित करें) जितना संभव हो उतना छोटा है। यदि बड़ा बहुभुज उत्तल है, तो n उत्तल आकृतियों की किसी भी अधिकतम व्यवस्था में, सभी छेद उत्तल होते हैं, और उनकी संख्या अधिक से अधिक होती है , और यह तंग है।[12]
क्षेत्र और परिधि को बराबर करना
निष्पक्ष बहुभुज विभाजन समस्या[20] एक (उत्तल) बहुभुज को (उत्तल) टुकड़ों में एक समान परिधि और समान क्षेत्र के साथ विभाजित करना है (यह निष्पक्ष केक काटने का एक विशेष मामला है)। किसी भी उत्तल बहुभुज को उत्तल टुकड़ों की किसी भी संख्या n में ठीक 1/n के क्षेत्रफल के साथ आसानी से काटा जा सकता है। हालांकि, यह सुनिश्चित करना कि टुकड़ों का क्षेत्रफल बराबर हो और परिमाप समान हो, अधिक चुनौतीपूर्ण है। इस समस्या को हल करने के लिए एल्गोरिदम हैं जब टुकड़ों की संख्या 2 की शक्ति होती है।[21] इस समस्या का एक सामान्यीकरण तब होता है जब क्षेत्र और परिधि के उपायों को क्रमशः शरीर पर और बहुभुज की सीमा पर माप के साथ बदल दिया जाता है। 2 और 3 टुकड़ों के लिए इस समस्या का अध्ययन किया गया।[22] किसी भी संख्या के उपायों को संभालने के लिए एक और सामान्यीकरण है।
अधिक सामान्य घटक आकार
टुकड़ों के अधिक सामान्य आकार का अध्ययन किया गया है, जिनमें सम्मलित हैं: सर्पिल आकार, स्टार बहुभुज और मोनोटोन बहुभुज। देखना [1]एक सर्वेक्षण के लिए।
यह भी देखें
- पॉलीगॉन कवरिंग - एक संबंधित समस्या जिसमें टुकड़ों को ओवरलैप करने की अनुमति दी जाती है।
- पैकिंग समस्याएँ - एक संबंधित समस्या जिसमें टुकड़ों को पूरी बड़ी वस्तु के भीतर फिट होना पड़ता है लेकिन उसे पूरी तरह से ढकना नहीं पड़ता।
- उत्तल नियमित बहुभुजों द्वारा यूक्लिडियन टाइलिंग - पूरे समतल को सरल बहुभुजों में विभाजित करने की समस्या जैसे कि आयतों के साथ टाइलिंग।
- वर्ग का वर्ग बनाना - केवल अन्य अभिन्न वर्गों का उपयोग करके एक अभिन्न वर्ग को विभाजित करने की समस्या।
- अंतरिक्ष विभाजन
- टाइलिंग पहेली - दिए गए कई टुकड़ों को दिए गए बड़े बहुभुज में पैक करने की पहेली।
- गिलोटिन विभाजन
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 1.4 Mark Keil, J. (2000). "Polygon Decomposition". कम्प्यूटेशनल ज्यामिति की पुस्तिका. pp. 491–518. doi:10.1016/B978-044482537-7/50012-7. ISBN 9780444825377.
- ↑ 2.0 2.1 Eppstein, David (2010). "Graph-Theoretic Solutions to Computational Geometry Problems". कंप्यूटर विज्ञान में ग्राफ-सैद्धांतिक अवधारणाएँ. Lecture Notes in Computer Science. Vol. 5911. pp. 1–16. CiteSeerX 10.1.1.249.5965. doi:10.1007/978-3-642-11409-0_1. ISBN 978-3-642-11408-3. S2CID 16353114.
- ↑ Realz Slaw. "वर्गों के साथ एक ओर्थोगोनल बहुभुज टाइलिंग". CS stack exchange. Retrieved 19 October 2015.
- ↑ 4.0 4.1 4.2 Andrzej Lingas and Ron Y Pinter and Ron L Rivest and Adi Shamir (1982). "सरल रेखीय बहुभुजों का न्यूनतम किनारा लंबाई विभाजन" (PDF). Proc. 20th Allerton Conf. Commun. Control Comput: 53–63.
- ↑ 5.0 5.1 5.2 Du, Ding-Zhu; Ko, Ker-I.; Hu, Xiaodong (2012). सन्निकटन एल्गोरिदम का डिजाइन और विश्लेषण. Springer Optimization and Its Applications (in English). New York: Springer-Verlag. pp. 165–209, chapter 5 "guillotine cut". ISBN 978-1-4614-1700-2.
- ↑ 6.0 6.1 Gonzalez, Teofilo; Zheng, Si-Qing (1985-06-01). "सरलरेखीय बहुभुजों के विभाजन की सीमाएँ". Proceedings of the First Annual Symposium on Computational Geometry. SCG '85. Baltimore, Maryland, USA: Association for Computing Machinery: 281–287. doi:10.1145/323233.323269. ISBN 978-0-89791-163-4. S2CID 12588297.
- ↑ Levcopoulos, C (1986-08-01). "बहुभुजों की न्यूनतम लंबाई वाले आयताकार विभाजनों के लिए तीव्र अनुमान". Proceedings of the Second Annual Symposium on Computational Geometry. SCG '86. Yorktown Heights, New York, USA: Association for Computing Machinery: 100–108. doi:10.1145/10515.10526. ISBN 978-0-89791-194-8. S2CID 16106423.
- ↑ Gonzalez, Teofilo F.; Razzazi, Mohammadreza; Zheng, Si-Qing (1993-12-01). "डी-बॉक्स में विभाजन के लिए एक कुशल डिवाइड-एंड-कॉनकर सन्निकटन एल्गोरिथम". International Journal of Computational Geometry & Applications. 03 (4): 417–428. doi:10.1142/S0218195993000269. ISSN 0218-1959.
- ↑ Gonzalez, Teofilo; Zheng, Si-Qing (1989-06-01). "आयताकार और गिलोटिन विभाजन के लिए बेहतर सीमाएँ". Journal of Symbolic Computation (in English). 7 (6): 591–610. doi:10.1016/S0747-7171(89)80042-2. ISSN 0747-7171.
- ↑ Arora, S. (October 1996). "यूक्लिडियन टीएसपी और अन्य ज्यामितीय समस्याओं के लिए बहुपद समय सन्निकटन योजनाएं". Proceedings of 37th Conference on Foundations of Computer Science: 2–11. doi:10.1109/SFCS.1996.548458. ISBN 0-8186-7594-2. S2CID 1499391.
- ↑ Mitchell, Joseph S. B. (1999-01-01). "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems". SIAM Journal on Computing. 28 (4): 1298–1309. doi:10.1137/S0097539796309764. ISSN 0097-5397.
- ↑ 12.0 12.1 Akopyan, Arseniy; Segal-Halevi, Erel (2018-01-01). "बहुभुज व्यवस्था में रिक्त स्थान की गणना". SIAM Journal on Discrete Mathematics. 32 (3): 2242–2257. arXiv:1604.00960. doi:10.1137/16M110407X. ISSN 0895-4801. S2CID 123397485.
- ↑ 13.0 13.1 Asano, Takao; Asano, Tetsuo; Imai, Hiroshi (1986). "एक बहुभुज क्षेत्र को ट्रेपेज़ोइड्स में विभाजित करना". Journal of the ACM. 33 (2): 290. doi:10.1145/5383.5387. hdl:2433/98478. S2CID 15296037.
- ↑ Chazelle, Bernard (2007). "रेखीय समय में एक साधारण बहुभुज को त्रिभुजित करना". Discrete & Computational Geometry. 6 (3): 485–524. doi:10.1007/bf02574703.
- ↑ H. Everett; W. Lenhart; M. Overmars; T. Shermer; J. Urrutia. (1992). "बहुभुजों का कड़ाई से उत्तल चतुर्भुज". Proc. 4th Canad. Conf. Comput. Geom. pp. 77–83.
- ↑ Ramaswami, Suneeta; Ramos, Pedro; Toussaint, Godfried (1998). "त्रिभुजों को चतुर्भुजों में बदलना". Computational Geometry. 9 (4): 257. doi:10.1016/s0925-7721(97)00019-9.
- ↑ Lingas, Andrzej; Levcopoulos, Christos; Sack, Jörg (1987). "बहुभुजों की न्यूनतम लंबाई वाले विभाजनों के लिए एल्गोरिदम". BIT. 27 (4): 474. doi:10.1007/bf01937272. S2CID 30936524.
- ↑ Levcopoulos, Christos; Lingas, Andrzej; Sack, Jörg-R. (1989). "इष्टतम बाइनरी सर्च ट्री और न्यूनतम वजन त्रिकोणासन समस्याओं के लिए ह्यूरिस्टिक्स". Theoretical Computer Science. 66 (2): 181. doi:10.1016/0304-3975(89)90134-5.
- ↑ Hertel, Stefan; Mehlhorn, Kurt (1983). Karpinski, Marek (ed.). "सरल बहुभुजों का तीव्र त्रिभुजन". Foundations of Computation Theory. Lecture Notes in Computer Science (in English). Berlin, Heidelberg: Springer. 158: 207–218. doi:10.1007/3-540-12689-9_105. ISBN 978-3-540-38682-7.
- ↑ Nandakumar, R.; Rao, N. Ramana (August 2012). "बहुभुजों का 'मेला' विभाजन - एक परिचय". Proceedings - Mathematical Sciences. 122 (3): 459–467. arXiv:0812.2241. doi:10.1007/s12044-012-0076-5. ISSN 0253-4142. S2CID 189909962.
- ↑ Armaselu, Bogdan; Daescu, Ovidiu (2015-11-23). "उत्तल बहुभुजों के निष्पक्ष विभाजन के लिए एल्गोरिदम". Theoretical Computer Science (in English). 607: 351–362. doi:10.1016/j.tcs.2015.08.003. ISSN 0304-3975.
- ↑ Bespamyatnikh, Sergei (2003). Akiyama, Jin; Kano, Mikio (eds.). "एक केक के विभाजन पर". Discrete and Computational Geometry. Lecture Notes in Computer Science (in English). Berlin, Heidelberg: Springer. 2866: 60–71. doi:10.1007/978-3-540-44400-8_7. ISBN 978-3-540-44400-8.
