बहुभुज विभाजन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (11 intermediate revisions by 3 users not shown) | |||
| Line 25: | Line 25: | ||
{{Main| छद्मत्रिभुज § छद्मत्रिकोण}} | {{Main| छद्मत्रिभुज § छद्मत्रिकोण}} | ||
समस्या के उन्हीं दो प्रकारों का अध्ययन उस स्थिति के लिए किया गया था जिसमें टुकड़े छद्म त्रिभुज होने चाहिए - बहुभुज जो त्रिभुजों की तरह तीन उत्तल शिखर होते हैं। भिन्नरूप होते हैं: सबसे छोटी संख्या में छद्मत्रिभुजों का विभाजन, और न्यूनतम कुल | समस्या के उन्हीं दो प्रकारों का अध्ययन उस स्थिति के लिए किया गया था जिसमें टुकड़े छद्म त्रिभुज होने चाहिए - बहुभुज जो त्रिभुजों की तरह तीन उत्तल शिखर होते हैं। भिन्नरूप होते हैं: सबसे छोटी संख्या में छद्मत्रिभुजों का विभाजन, और न्यूनतम कुल कोणों की लंबाई के साथ [[छद्मत्रिकोण|छद्मत्रिकोणों]] का विभाजन होता है । | ||
== एक आयताकार बहुभुज को आयतों में विभाजित करना == | == एक आयताकार बहुभुज को आयतों में विभाजित करना == | ||
| Line 36: | Line 36: | ||
एक आयताकार बहुभुज को वर्गों की सबसे छोटी संख्या में विभाजित करने की समस्या (स्वैच्छिक आयतों के विपरीत) एनपी- ठोस होता है।<ref name="Slaw2013">{{cite web|author=Realz Slaw|title=वर्गों के साथ एक ओर्थोगोनल बहुभुज टाइलिंग|url=https://cs.stackexchange.com/q/16801|access-date=19 October 2015|publisher=CS stack exchange}}</ref> | एक आयताकार बहुभुज को वर्गों की सबसे छोटी संख्या में विभाजित करने की समस्या (स्वैच्छिक आयतों के विपरीत) एनपी- ठोस होता है।<ref name="Slaw2013">{{cite web|author=Realz Slaw|title=वर्गों के साथ एक ओर्थोगोनल बहुभुज टाइलिंग|url=https://cs.stackexchange.com/q/16801|access-date=19 October 2015|publisher=CS stack exchange}}</ref> | ||
=== कुल | === कुल कोणों की लंबाई को कम करना === | ||
कुछ अनुप्रयोगों में, कर्त की कुल लंबाई को कम करना अधिक महत्वपूर्ण होता है (उदाहरण के लिए विभाजन करने की लागत को कम करने के लिए, या धूल की मात्रा को कम करने के लिए)। इस समस्या को न्यूनतम | कुछ अनुप्रयोगों में, कर्त की कुल लंबाई को कम करना अधिक महत्वपूर्ण होता है (उदाहरण के लिए विभाजन करने की लागत को कम करने के लिए, या धूल की मात्रा को कम करने के लिए)। इस समस्या को न्यूनतम कोणों-लंबाई का आयताकार विभाजन कहा जाता है। 1982 में लिंगास, पिंटर, रिवेस्ट और शमीर द्वारा पहली बार इसका अध्ययन किया था।<ref name=":0">{{Cite journal|last=Andrzej Lingas and Ron Y Pinter and Ron L Rivest and Adi Shamir|date=1982|title=सरल रेखीय बहुभुजों का न्यूनतम किनारा लंबाई विभाजन|url=https://people.csail.mit.edu/rivest/pubs/LPRS82.pdf|journal=Proc. 20th Allerton Conf. Commun. Control Comput|volume=|pages=53–63|via=}}</ref><ref name=":1">{{Cite book|last1=Du|first1=Ding-Zhu|url=https://www.springer.com/gp/book/9781461417002|title=सन्निकटन एल्गोरिदम का डिजाइन और विश्लेषण|last2=Ko|first2=Ker-I.|last3=Hu|first3=Xiaodong|date=2012|publisher=Springer-Verlag|isbn=978-1-4614-1700-2|series=Springer Optimization and Its Applications|location=New York|pages=165–209, chapter 5 "guillotine cut"|language=en}}</ref> इस समस्या की कार्य अवधि जटिलता महत्वपूर्ण रूप से लगातार काम करते आये है कि अनिर्मित बहुभुज में छिद्र होने की अनुमति है या नहीं। | ||
यदि अपरिष्कृ बहुभुज छिद्र अनुपयोगी है, तो समय पर इष्टतम विभाजन किया जा सकता है <math>O(n^4)</math>, जहां n बहुभुज के शीर्षों की संख्या है। "हिस्टोग्राम बहुभुज" के विशेष स्थिति में, लक्षणो में सुधार होता है <math>O(n^3)</math><ref name=":0" /> एल्गोरिथ्म [[गतिशील प्रोग्रामिंग]] का उपयोग करता है और निम्नलिखित तथ्य पर निर्भर करता है: यदि बहुभुज छिद्र -मुक्त है, तो इसमें एक न्यूनतम-लंबाई वाला विभाजन होता है जिसमें प्रत्येक अधिकतम रेखा-खंड में सीमा का एक शीर्ष होता है। इसका कारण यह है कि, किसी भी न्यूनतम-लंबाई वाले विभाजन में, प्रत्येक अधिकतम रेखा-खंड को धकेला जा सकता है, जब तक कि यह कुल लंबाई को बदले बिना सीमा के किसी एक कोने से टकराता है। इसलिए केवल <math>O(n^2)</math> संभावित विभाजन में एक रेखा खंड के लिए सक्रिय, और उन्हें गतिक प्रोग्रामिंग का उपयोग करके कुशलता से जांचा जा सकता है।<ref name=":1" />{{Rp|166–167}} | यदि अपरिष्कृ बहुभुज छिद्र अनुपयोगी है, तो समय पर इष्टतम विभाजन किया जा सकता है <math>O(n^4)</math>, जहां n बहुभुज के शीर्षों की संख्या है। "हिस्टोग्राम बहुभुज" के विशेष स्थिति में, लक्षणो में सुधार होता है <math>O(n^3)</math><ref name=":0" /> एल्गोरिथ्म [[गतिशील प्रोग्रामिंग]] का उपयोग करता है और निम्नलिखित तथ्य पर निर्भर करता है: यदि बहुभुज छिद्र -मुक्त है, तो इसमें एक न्यूनतम-लंबाई वाला विभाजन होता है जिसमें प्रत्येक अधिकतम रेखा-खंड में सीमा का एक शीर्ष होता है। इसका कारण यह है कि, किसी भी न्यूनतम-लंबाई वाले विभाजन में, प्रत्येक अधिकतम रेखा-खंड को धकेला जा सकता है, जब तक कि यह कुल लंबाई को बदले बिना सीमा के किसी एक कोने से टकराता है। इसलिए केवल <math>O(n^2)</math> संभावित विभाजन में एक रेखा खंड के लिए सक्रिय, और उन्हें गतिक प्रोग्रामिंग का उपयोग करके कुशलता से जांचा जा सकता है।<ref name=":1" />{{Rp|166–167}} | ||
यदि अपरिष्कृ बहुभुज में छिद्र हो सकते हैं, यदि वे | यदि अपरिष्कृ बहुभुज में छिद्र हो सकते हैं, यदि वे विकृत छिद्र (अर्थात , एकल बिंदु) हों, तो समस्या एनपी-हार्ड होती है। इसे [[प्लानर सैट|समतलीय सैट]] से घटाकर सिद्ध किया जा सकता है।<ref name=":0" /><ref name=":3">{{Cite journal|last1=Gonzalez|first1=Teofilo|last2=Zheng|first2=Si-Qing|date=1985-06-01|title=सरलरेखीय बहुभुजों के विभाजन की सीमाएँ|url=https://doi.org/10.1145/323233.323269|journal=Proceedings of the First Annual Symposium on Computational Geometry|series=SCG '85|location=Baltimore, Maryland, USA|publisher=Association for Computing Machinery|pages=281–287|doi=10.1145/323233.323269|isbn=978-0-89791-163-4|s2cid=12588297}}</ref> उस स्थिति के लिए जिसमें सभी छिद्र एकल बिंदु होते हैं, कई स्थिर-कारक सन्निकटन विकसित किए गए हैं: | ||
* A (3+sqrt(3)) समय में सन्निकटन <math>O(n^2)</math>;<ref name=":3" /> | * A (3+sqrt(3)) समय में सन्निकटन <math>O(n^2)</math>;<ref name=":3" /> | ||
| Line 47: | Line 47: | ||
* समय में एक 4 सन्निकटन <math>O(n \log{n})</math> (अधिक सामान्यतः, ''d'' आयामों में, यह एक है <math>2 d</math> समय में सन्निकटन <math>O(d n \log{n})</math>),<ref>{{Cite journal|last1=Gonzalez|first1=Teofilo F.|last2=Razzazi|first2=Mohammadreza|last3=Zheng|first3=Si-Qing|date=1993-12-01|title=डी-बॉक्स में विभाजन के लिए एक कुशल डिवाइड-एंड-कॉनकर सन्निकटन एल्गोरिथम|url=https://www.worldscientific.com/doi/abs/10.1142/S0218195993000269|journal=International Journal of Computational Geometry & Applications|volume=03|issue=4|pages=417–428|doi=10.1142/S0218195993000269|issn=0218-1959}}</ref> | * समय में एक 4 सन्निकटन <math>O(n \log{n})</math> (अधिक सामान्यतः, ''d'' आयामों में, यह एक है <math>2 d</math> समय में सन्निकटन <math>O(d n \log{n})</math>),<ref>{{Cite journal|last1=Gonzalez|first1=Teofilo F.|last2=Razzazi|first2=Mohammadreza|last3=Zheng|first3=Si-Qing|date=1993-12-01|title=डी-बॉक्स में विभाजन के लिए एक कुशल डिवाइड-एंड-कॉनकर सन्निकटन एल्गोरिथम|url=https://www.worldscientific.com/doi/abs/10.1142/S0218195993000269|journal=International Journal of Computational Geometry & Applications|volume=03|issue=4|pages=417–428|doi=10.1142/S0218195993000269|issn=0218-1959}}</ref> | ||
* समय में 3 सन्निकटन <math>O(n^4)</math>; | * समय में 3 सन्निकटन <math>O(n^4)</math>; | ||
* समय में 1.75 सन्निकटन <math>O(n^5)</math> (अधिक सामान्यतः, ''d'' आयामों में, यह एक होती है <math>2d-4+4/d</math> समय में सन्निकटन <math>O(d n^{2 d + 1})</math>);<ref name=":2">{{Cite journal|last1=Gonzalez|first1=Teofilo|last2=Zheng|first2=Si-Qing|date=1989-06-01|title=आयताकार और गिलोटिन विभाजन के लिए बेहतर सीमाएँ|journal=Journal of Symbolic Computation|language=en|volume=7|issue=6|pages=591–610|doi=10.1016/S0747-7171(89)80042-2|issn=0747-7171|doi-access=free}}</ref> बाद वाला सन्निकटन [[गिलोटिन विभाजन]] नामक समस्या के प्रतिबंधित संस्करण का उपयोग करता है, जिसमें कट गिलोटिन कट्स (एज-टू-एज कट) | * समय में 1.75 सन्निकटन <math>O(n^5)</math> (अधिक सामान्यतः, ''d'' आयामों में, यह एक होती है <math>2d-4+4/d</math> समय में सन्निकटन <math>O(d n^{2 d + 1})</math>);<ref name=":2">{{Cite journal|last1=Gonzalez|first1=Teofilo|last2=Zheng|first2=Si-Qing|date=1989-06-01|title=आयताकार और गिलोटिन विभाजन के लिए बेहतर सीमाएँ|journal=Journal of Symbolic Computation|language=en|volume=7|issue=6|pages=591–610|doi=10.1016/S0747-7171(89)80042-2|issn=0747-7171|doi-access=free}}</ref> बाद वाला सन्निकटन [[गिलोटिन विभाजन]] नामक समस्या के प्रतिबंधित संस्करण का उपयोग करता है, जिसमें कट '''गिलोटिन कट्स''' (एज-टू-एज कट) की सही श्रंखला होनी चाहिए। | ||
* त्रुटिहीन गिलोटिन | * त्रुटिहीन गिलोटिन कट का उपयोग करते हुए कई [[बहुपद-समय सन्निकटन योजना]]एं होती है।<ref>{{Cite journal|last=Arora|first=S.|date=October 1996|title=यूक्लिडियन टीएसपी और अन्य ज्यामितीय समस्याओं के लिए बहुपद समय सन्निकटन योजनाएं|url=https://ieeexplore.ieee.org/document/548458|journal=Proceedings of 37th Conference on Foundations of Computer Science|pages=2–11|doi=10.1109/SFCS.1996.548458|isbn=0-8186-7594-2|s2cid=1499391}}</ref><ref>{{Cite journal|last=Mitchell|first=Joseph S. B.|date=1999-01-01|title=Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems|url=https://epubs.siam.org/doi/abs/10.1137/S0097539796309764|journal=SIAM Journal on Computing|volume=28|issue=4|pages=1298–1309|doi=10.1137/S0097539796309764|issn=0097-5397}}</ref><ref name=":1" /> | ||
=== रिक्त स्थान की संख्या कम करना === | === रिक्त स्थान की संख्या कम करना === | ||
इस समुच्चयन में, बड़े बहुभुज में पहले से ही कुछ युग्मानूसार-असंबद्ध आयत सम्मलित होते हैं। उद्देश्य | इस समुच्चयन में, बड़े बहुभुज में पहले से ही कुछ युग्मानूसार-असंबद्ध आयत सम्मलित होते हैं। उद्देश्य बहुसंख्यक विभाजन को आयतों में इस तरह सम्मलित किया है जैसे कि प्रत्येक मूल आयत खण्ड़ो में समाहित होता है, और इसके अधीन, "रिक्त स्थान" की संख्या (टुकड़े जिनमें मूल आयत नहीं होते है) जितना संभव हो उतना छोटा है। निम्नलिखित परिणाम ज्ञात हैं:<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> आयताकार, और यह घन होता है। | ||
== एक बहुभुज को [[चतुर्भुज]] में विभाजित करें == | == एक बहुभुज को [[चतुर्भुज]] में विभाजित करें == | ||
वीएलएसआई | वीएलएसआई आर्टवर्क प्रोसेसिंग सिस्टम में, बहुधा एक बहुभुज क्षेत्र को दो क्षैतिज भुजाओ के साथ ट्रैपेज़ोइड्स की न्यूनतम संख्या में विभाजित करने की आवश्यकता होती है। एक क्षैतिज भुजा वाले त्रिभुज को दो क्षैतिज भुजाओं वाला एक समलम्बाकार माना जाता है, जिनमें से एक विकृत होता है। एक छिद्र -मुक्त बहुभुज के साथ <math>n</math> भुजाओ मे, इस तरह का सबसे छोटा विभाजन समय में पाया जा सकता है<math>O(n^2)</math>.<ref name=Asano1986/> | ||
यदि समलम्बाभ की संख्या कम से कम नहीं होनी चाहिए, तो समय पर | यदि समलम्बाभ की संख्या कम से कम नहीं होनी चाहिए, तो समय पर चतुर्भुज पाया जा सकता है <math>O(n)</math>, बहुभुज त्रिभुज एल्गोरिथम के उपोत्पाद के रूप में होता है ।<ref name=Chazelle1991>{{Cite journal|doi=10.1007/bf02574703|title=रेखीय समय में एक साधारण बहुभुज को त्रिभुजित करना|journal=[[Discrete & Computational Geometry]]|volume=6|issue=3|pages=485–524|year=2007|last1=Chazelle|first1=Bernard|doi-access=free}}</ref> | ||
यदि बहुभुज में छिद्र होते हैं, तो समस्या एनपी-पूर्ण है, किन्तु | यदि बहुभुज में छिद्र होते हैं, तो समस्या एनपी-पूर्ण है, किन्तु समय में 3-सन्निकटन के रूप मे पाया जा सकता है <math>O(n\log n)</math>.<ref name="Asano1986">{{Cite journal|doi=10.1145/5383.5387 |title=एक बहुभुज क्षेत्र को ट्रेपेज़ोइड्स में विभाजित करना|journal=Journal of the ACM |volume=33 |issue=2 |pages=290 |year=1986 |last1=Asano |first1=Takao |last2=Asano |first2=Tetsuo |last3=Imai |first3=Hiroshi |hdl=2433/98478 |s2cid=15296037 |hdl-access=free }}</ref> | ||
== एक बहुभुज को उत्तल चतुर्भुजों में विभाजित करें == | == एक बहुभुज को उत्तल चतुर्भुजों में विभाजित करें == | ||
एक चतुर्भुज या चतुष्कोण चतुर्भुज में एक विभाजन | एक चतुर्भुज या चतुष्कोण चतुर्भुज में एक विभाजन है। | ||
चचतुष्कोणीय समस्याओं की एक आवर्ती विशेषता यह है कि क्या वे स्टीनर बिंदु की अनुमति देते हैं, अर्थात, क्या एल्गोरिथ्म को उन बिंदुओं को जोड़ने की अनुमति है जो बहुभुज के कोने नहीं होते हैं। स्टाइनर बिन्दु की अनुमति देने से छोटे डिवीजनों को सक्षम किया जा सकता है, लेकिन फिर यह गारंटी देना अधिक कठिन है कि एल्गोरिदम द्वारा पाए गए डिवीजनों का न्यूनतम आकार है। | |||
स्टेनर बिंदुओं के साथ छिद्र -मुक्त बहुभुजों के चतुष्कोणों के लिए रैखिक-समय एल्गोरिदम हैं, किन्तु | स्टेनर बिंदुओं के साथ छिद्र -मुक्त बहुभुजों के चतुष्कोणों के लिए रैखिक-समय एल्गोरिदम हैं, किन्तु सबसे छोटा विभाजन खोजने की गारंटी नहीं है।<ref name="Everett1992">{{cite conference | title=बहुभुजों का कड़ाई से उत्तल चतुर्भुज|author1=H. Everett |author2=W. Lenhart |author3=M. Overmars |author4=T. Shermer |author5=J. Urrutia. | book-title=Proc. 4th Canad. Conf. Comput. Geom. | year=1992 | pages=77–83}}</ref><ref name=Ramaswami1998>{{Cite journal|doi=10.1016/s0925-7721(97)00019-9|title=त्रिभुजों को चतुर्भुजों में बदलना|journal=[[Computational Geometry (journal)|Computational Geometry]]|volume=9|issue=4|pages=257|year=1998|last1=Ramaswami|first1=Suneeta|last2=Ramos|first2=Pedro|last3=Toussaint|first3=Godfried|doi-access=free}}</ref> | ||
== एक बहुभुज को ''m''-gons में विभाजित करें == | == एक बहुभुज को ''m''-gons में विभाजित करें == | ||
पिछली समस्याओं का | पिछली समस्याओं का सामान्यीकरण उन बहुभुजों में विभाजन करना होता है जिनकी ठीक ''m'' भुजाएँ हैं, या अधिकतम ''m'' भुजाएँ हैं। यहाँ उद्देश्य कुल कोणों की लंबाई को कम करना है। इस समस्या को ''n'' और ''m'' में समय बहुपद में हल किया जा सकता है।<ref name="Lingas1987">{{Cite journal|doi=10.1007/bf01937272|title=बहुभुजों की न्यूनतम लंबाई वाले विभाजनों के लिए एल्गोरिदम|journal=BIT|volume=27|issue=4|pages=474|year=1987|last1=Lingas|first1=Andrzej|last2=Levcopoulos|first2=Christos|last3=Sack|first3=Jörg|s2cid=30936524}}</ref><ref name="Levcopoulos1989">{{Cite journal|doi=10.1016/0304-3975(89)90134-5|title=इष्टतम बाइनरी सर्च ट्री और न्यूनतम वजन त्रिकोणासन समस्याओं के लिए ह्यूरिस्टिक्स|journal=Theoretical Computer Science|volume=66|issue=2|pages=181|year=1989|last1=Levcopoulos|first1=Christos|last2=Lingas|first2=Andrzej|last3=Sack|first3=Jörg-R.|doi-access=free}}</ref> | ||
== एक बहुभुज को उत्तल बहुभुजों में विभाजित करें == | == एक बहुभुज को उत्तल बहुभुजों में विभाजित करें == | ||
उत्तल बहुभुजों में एक सामान्य बहुभुज का विभाजन करते समय, कई उद्देश्यों का अध्ययन किया गया है। | उत्तल बहुभुजों में एक सामान्य बहुभुज का विभाजन करते समय, कई उद्देश्यों का अध्ययन किया गया है। | ||
=== घटकों की संख्या को कम करना === | === घटकों की संख्या को कम करना === | ||
इष्टतम उत्तल विभाजन समस्या एक गैर-[[उत्तल बहुभुज]] को यथासंभव कुछ उत्तल बहुभुजों में विभाजित करता है, केवल प्रारंभिक बहुभुज के | इष्टतम उत्तल विभाजन समस्या एक गैर-[[उत्तल बहुभुज]] को यथासंभव कुछ उत्तल बहुभुजों में विभाजित करता है, केवल प्रारंभिक बहुभुज के शीर्ष का उपयोग करना। इस समस्या के लिए त्रुटिहीन और अनुमानित एल्गोरिदम हैं।<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>, और यह | मूल बहुभुज में पहले से ही कुछ युग्मानूसार-असंबद्ध उत्तल आकृतियाँ होती हैं, और उद्देश्य से इसे उत्तल बहुभुजों में विभाजित करना होता है, अर्थात प्रत्येक मूल आकृति खण्ड़ो में से एक में समाहित हो, और इसके अधीन, रिक्त स्थानों की संख्या (टुकड़े जो नहीं एक मूल आंकड़ा सम्मलित करें) जितना संभव हो उतना छोटा होता है। यदि बड़ा बहुभुज उत्तल है, तो 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> | |||
इस समस्या का एक सामान्यीकरण तब होता है जब क्षेत्र और परिधि के उपायों को क्रमशः तत्व पर और बहुभुज की सीमा पर माप के साथ बदल दिया जाता है। 2 और 3 खण्ड़ो के लिए इस समस्या का अध्ययन किया गया है ।<ref>{{Cite journal|last=Bespamyatnikh|first=Sergei|date=2003|editor-last=Akiyama|editor-first=Jin|editor2-last=Kano|editor2-first=Mikio|title=एक केक के विभाजन पर|url=https://link.springer.com/chapter/10.1007/978-3-540-44400-8_7|journal=Discrete and Computational Geometry|series=Lecture Notes in Computer Science|language=en|location=Berlin, Heidelberg|publisher=Springer|volume=2866|pages=60–71|doi=10.1007/978-3-540-44400-8_7|isbn=978-3-540-44400-8}}</ref> | इस समस्या का एक सामान्यीकरण तब होता है जब क्षेत्र और परिधि के उपायों को क्रमशः तत्व पर और बहुभुज की सीमा पर माप के साथ बदल दिया जाता है। 2 और 3 खण्ड़ो के लिए इस समस्या का अध्ययन किया गया है ।<ref>{{Cite journal|last=Bespamyatnikh|first=Sergei|date=2003|editor-last=Akiyama|editor-first=Jin|editor2-last=Kano|editor2-first=Mikio|title=एक केक के विभाजन पर|url=https://link.springer.com/chapter/10.1007/978-3-540-44400-8_7|journal=Discrete and Computational Geometry|series=Lecture Notes in Computer Science|language=en|location=Berlin, Heidelberg|publisher=Springer|volume=2866|pages=60–71|doi=10.1007/978-3-540-44400-8_7|isbn=978-3-540-44400-8}}</ref> | ||
| Line 84: | Line 84: | ||
== अधिक सामान्य घटक आकार == | == अधिक सामान्य घटक आकार == | ||
खण्ड़ो | खण्ड़ो के अधिक सामान्य आकार का अध्ययन किया गया है, जिनमें सम्मलित हैं: सर्पिल आकार, स्टार बहुभुज और [[मोनोटोन बहुभुज]]। <ref name="Keil2000" /> एक सर्वेक्षण के लिए [देखें। | ||
== यह भी देखें == | == यह भी देखें == | ||
| Line 97: | Line 97: | ||
==संदर्भ== | ==संदर्भ== | ||
{{reflist}} | {{reflist}} | ||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | |||
[[Category:CS1 English-language sources (en)]] | |||
[[Category: | |||
[[Category:Created On 05/05/2023]] | [[Category:Created On 05/05/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:कम्प्यूटेशनल ज्यामिति]] | |||
[[Category:पैकिंग की समस्या]] | |||
[[Category:बहुभुज]] | |||
Latest revision as of 16:26, 24 May 2023
ज्यामिति में, बहुभुज विभाजन मे एक अभाज्य इकाइयों (जैसे वर्ग) का एक समूह होता है, जो अतिव्याप्त नहीं होता है और जिसका संयोजन बहुभुज के बराबर होता है। बहुविभाजन समस्या एक ऐसे विभाजन को जाँचने की समस्या है जो किसी अर्थ में न्यूनतम होता है, उदाहरण के लिए इकाइयों की सबसे छोटी संख्या वाला विभाजन या या सबसे छोटी कुल पार्श्व-लंबाई वाली इकाइयाँ होता है।
बहुभुज विभाजन अभिकलात्मक ज्यामिति से संबंधित एक महत्वपूर्ण वर्ग है। कई अलग-अलग बहुविभाजन समस्याएं हैं, विभाजन बहुसंख्यक प्रकार के होते है और विभाजन में अनुमत इकाइयों के प्रकार पर निर्भर करता है।
बहुभुज अपघटन शब्द का प्रयोग अधिकांशतः सामान्य शब्द के रूप में किया जाता है जिसमें बहुभुज आवरण और विभाजन दोनों सम्मलित होते हैं।[1]
अनुप्रयोग
बहुभुज अपघटन कई क्षेत्रों में लागू होता है: [1]
*अभिरचना पहचान तकनीक किसी वस्तु का वर्णन, पहचान या वर्गीकरण करने के लिए उससे जानकारी निकालती है। एक सामान्य बहुसंख्यक वस्तु को पहचानने के लिए एक स्थापित योजना यह होती है कि इसे सरल घटकों मे विघटित किया जाए, फिर घटकों और उनके अंतर्संबंधों की पहचान की जाए और इस जानकारी का उपयोग वस्तु के आकार को निर्धारित करने के लिए किया जाए।
- वीएलएसआई प्रोजेक्ट डाटा प्रसंस्करण में, लेआउट को बहुभुज के रूप में दर्शाया जाता है, और इलेक्ट्रॉन-बीम लिथोग्राफी की तैयारी के लिए इन बहुरूपताओ को बहुभुज क्षेत्रों को मौलिक आंकड़ों में विघटित करना होता है। परिच्छेदन क्षेत्र को चैनलों में विभाजित करने की प्रक्रिया में बहुभुज अपघटन का भी उपयोग किया जाता है।
- कम्प्यूटेशनल ज्यामिति में, सामान्य बहुसंख्यक समस्याओं के लिए एल्गोरिदम अधिकांशतः प्रतिबंधित प्रकार के बहुभुज जैसे कि उत्तल या तारे के आकार के लिए अधिक जटिल होते हैं। पॉइंट-इन- बहुभुज समस्या इसका एक उदाहरण है। सामान्य बहुभुजों पर इस प्रकार की कुछ समस्याओं को हल करने की एक रणनीति है कि बहुभुज को सरल घटक भागों में विघटित किया जाए, एक विशेष एल्गोरिथम का उपयोग करके प्रत्येक घटक पर समस्या को हल किया जाए, और फिर आंशिक समाधानों को संयोजित किया जाए।
- अन्य अनुप्रयोगों में डेटा कम्प्रेशन डेटाबेस प्रणाली, प्रतिबिंब प्रक्रमण और कंप्यूटर चित्रलेख सम्मलित होते हैं।
एक बहुभुज को त्रिभुजों में विभाजित करना
मूख्य रुप से अध्ययन की गई बहुभुज विभाजन समस्या त्रिकोणों की एक छोटी संख्या में विभाजन होत है, जिसे त्रिकोणासन भी कहा जाता है। एक छिद्र-मुक्त बहुभुज के साथ कोने होते है, एक त्रिभुज की गणना समय मे की जा सकती है । छिद्र वाले बहुभुज के लिए, निम्न सीमा होती है