बहुभुज विभाजन: Difference between revisions
From Vigyanwiki
No edit summary |
|||
| (28 intermediate revisions by 3 users not shown) | |||
| 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> | |||
== अनुप्रयोग == | == अनुप्रयोग == | ||
बहुभुज अपघटन कई क्षेत्रों में लागू होता है: <ref name=Keil2000/> | बहुभुज अपघटन कई क्षेत्रों में लागू होता है: <ref name=Keil2000/> | ||
<nowiki>*</nowiki> | <nowiki>*</nowiki>अभिरचना पहचान तकनीक किसी वस्तु का वर्णन, पहचान या वर्गीकरण करने के लिए उससे जानकारी निकालती है। एक सामान्य बहुसंख्यक वस्तु को पहचानने के लिए एक स्थापित योजना यह होती है कि इसे सरल घटकों मे विघटित किया जाए, फिर घटकों और उनके अंतर्संबंधों की पहचान की जाए और इस जानकारी का उपयोग वस्तु के आकार को निर्धारित करने के लिए किया जाए। | ||
* [[वीएलएसआई]] | * [[वीएलएसआई]] प्रोजेक्ट डाटा प्रसंस्करण में, लेआउट को बहुभुज के रूप में दर्शाया जाता है, और इलेक्ट्रॉन-बीम लिथोग्राफी की तैयारी के लिए इन बहुरूपताओ को बहुभुज क्षेत्रों को मौलिक आंकड़ों में विघटित करना होता है। परिच्छेदन क्षेत्र को चैनलों में विभाजित करने की प्रक्रिया में बहुभुज अपघटन का भी उपयोग किया जाता है। | ||
* कम्प्यूटेशनल ज्यामिति में, सामान्य | * कम्प्यूटेशनल ज्यामिति में, सामान्य बहुसंख्यक समस्याओं के लिए एल्गोरिदम अधिकांशतः प्रतिबंधित प्रकार के बहुभुज जैसे कि उत्तल या तारे के आकार के लिए अधिक जटिल होते हैं। पॉइंट-इन- बहुभुज समस्या इसका एक उदाहरण है। सामान्य बहुभुजों पर इस प्रकार की कुछ समस्याओं को हल करने की एक रणनीति है कि बहुभुज को सरल घटक भागों में विघटित किया जाए, एक विशेष एल्गोरिथम का उपयोग करके प्रत्येक घटक पर समस्या को हल किया जाए, और फिर आंशिक समाधानों को संयोजित किया जाए। | ||
* अन्य अनुप्रयोगों में डेटा कम्प्रेशन [[डेटाबेस सिस्टम|डेटाबेस प्रणाली]], [[ मूर्ति प्रोद्योगिकी |प्रतिबिंब प्रक्रमण]] | * अन्य अनुप्रयोगों में डेटा कम्प्रेशन [[डेटाबेस सिस्टम|डेटाबेस प्रणाली]], [[ मूर्ति प्रोद्योगिकी |प्रतिबिंब प्रक्रमण]] और [[ कंप्यूटर चित्रलेख |कंप्यूटर चित्रलेख]] सम्मलित होते हैं। | ||
== एक बहुभुज को त्रिभुजों में विभाजित करना == | == एक बहुभुज को त्रिभुजों में विभाजित करना == | ||
{{Main|बहुभुज त्रिभुज | {{Main|बहुभुज त्रिभुज | ||
|न्यूनतम | |न्यूनतम भार त्रिकोण}} | ||
मूख्य रुप से अध्ययन की गई बहुभुज विभाजन समस्या त्रिकोणों की एक छोटी संख्या में विभाजन | मूख्य रुप से अध्ययन की गई बहुभुज विभाजन समस्या त्रिकोणों की एक छोटी संख्या में विभाजन होत है, जिसे '''त्रिकोणासन''' भी कहा जाता है। एक छिद्र-मुक्त बहुभुज के साथ <math>n</math> कोने होते है, एक त्रिभुज की गणना समय मे की जा सकती है <math>\Theta(n)</math>। छिद्र वाले बहुभुज के लिए, निम्न सीमा होती है <math>\Omega(n \log n)</math>। | ||
एक सम्बद्धित समस्या न्यूनतम कुल छोर की लंबाई वाले त्रिकोणों में विभाजन करती है, जिसे न्यूनतम-भार त्रिकोणासन भी कहा जाता है। | एक सम्बद्धित समस्या न्यूनतम कुल छोर की लंबाई वाले त्रिकोणों में विभाजन करती है, जिसे '''न्यूनतम-भार त्रिकोणासन''' भी कहा जाता है। | ||
== एक बहुभुज को छद्म-त्रिकोणों में विभाजित करना == | == एक बहुभुज को छद्म-त्रिकोणों में विभाजित करना == | ||
{{Main| छद्मत्रिभुज § | {{Main| छद्मत्रिभुज § छद्मत्रिकोण}} | ||
समस्या के | समस्या के उन्हीं दो प्रकारों का अध्ययन उस स्थिति के लिए किया गया था जिसमें टुकड़े छद्म त्रिभुज होने चाहिए - बहुभुज जो त्रिभुजों की तरह तीन उत्तल शिखर होते हैं। भिन्नरूप होते हैं: सबसे छोटी संख्या में छद्मत्रिभुजों का विभाजन, और न्यूनतम कुल कोणों की लंबाई के साथ [[छद्मत्रिकोण|छद्मत्रिकोणों]] का विभाजन होता है । | ||
== एक आयताकार बहुभुज को आयतों में विभाजित करना == | == एक आयताकार बहुभुज को आयतों में विभाजित करना == | ||
बहुविभाजित समस्याओं की एक विशेष उप-श्रेणी तब उत्पन्न होती है जब बड़ा बहुभुज '''सरल रेखीय बहुभुज''' होता है (जिसे: ओर्थोगोनल बहुभुज भी कहा जाता है)। इस स्थिति में, विचार करने के लिए सबसे महत्वपूर्ण घटक आकार आयत होता है।<ref name=Keil2000/> | |||
आयताकार विभाजन में कई अनुप्रयोग होते हैं। वीएलएसआई डिजाइन में, लिथोग्राफिक पैटर्न जनरेटर में उपलब्ध सरल आकृतियों में आवरण को विघटित करना आवश्यक होता है, और इसी तरह की आवरण अपघटन की समस्या [[डीएनए]] माइक्रोएरे डिजाइन में भी उत्पन्न होती है। आयताकार विभाजन प्रतिबिंब प्रक्रमण में [[कनवल्शन|संवलन]] संक्रिया को आसान बना सकते हैं और [[ बिटमैप चित्र |बिटमैप चित्र]] को संपीडन, करने के लिए उपयोग किया जा सकता है। अतिसंबद्ध मैट्रिक्स अपघटन की | आयताकार विभाजन में कई अनुप्रयोग होते हैं। वीएलएसआई डिजाइन में, लिथोग्राफिक पैटर्न जनरेटर में उपलब्ध सरल आकृतियों में आवरण को विघटित करना आवश्यक होता है, और इसी तरह की आवरण अपघटन की समस्या [[डीएनए]] माइक्रोएरे डिजाइन में भी उत्पन्न होती है। आयताकार विभाजन प्रतिबिंब प्रक्रमण में [[कनवल्शन|संवलन]] संक्रिया को आसान बना सकते हैं और [[ बिटमैप चित्र |बिटमैप चित्र]] को संपीडन, करने के लिए उपयोग किया जा सकता है। अतिसंबद्ध मैट्रिक्स अपघटन की योजनाओं को [[विकिरण चिकित्सा]] योजना पर लागू किया गया है, और रोबोट स्वसमुच्चय अनुक्रमों को डिजाइन करने के लिए आयताकार विभाजन का भी उपयोग किया गया है।<ref name=Eppstein2009>{{Cite book|doi=10.1007/978-3-642-11409-0_1|chapter=Graph-Theoretic Solutions to Computational Geometry Problems|title=कंप्यूटर विज्ञान में ग्राफ-सैद्धांतिक अवधारणाएँ|volume=5911|pages=1–16|series=Lecture Notes in Computer Science|year=2010|last1=Eppstein|first1=David|isbn=978-3-642-11408-3|citeseerx=10.1.1.249.5965|s2cid=16353114}}</ref> | ||
=== घटकों की संख्या को कम करना === | === घटकों की संख्या को कम करना === | ||
घटकों के आयतों की संख्या को कम करने की समस्या बहुपद होती है: कई बहुपद समय ऐल्गोरिथ्म ज्ञात हैं। देखो <ref name=Keil2000/>{{rp|10–13}} और <ref name=Eppstein2009/>{{rp|3–5}} सर्वेक्षण के लिए होता है। | |||
एक | एक आयताकार बहुभुज को वर्गों की सबसे छोटी संख्या में विभाजित करने की समस्या (स्वैच्छिक आयतों के विपरीत) एनपी- ठोस होता है।<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}} | |||
यदि अपरिष्कृ बहुभुज में छिद्र हो सकते हैं, यदि वे विकृत छिद्र (अर्थात , एकल बिंदु) हों, तो समस्या एनपी-हार्ड होती है। इसे [[प्लानर सैट|समतलीय सैट]] से घटाकर सिद्ध किया जा सकता है।<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 \log{n})</math>;<ref>{{Cite journal|last=Levcopoulos|first=C|date=1986-08-01|title=बहुभुजों की न्यूनतम लंबाई वाले आयताकार विभाजनों के लिए तीव्र अनुमान|journal=Proceedings of the Second Annual Symposium on Computational Geometry|series=SCG '86|location=Yorktown Heights, New York, USA|publisher=Association for Computing Machinery|pages=100–108|doi=10.1145/10515.10526|isbn=978-0-89791-194-8|s2cid=16106423|doi-access=free}}</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> | |||
* | |||
* समय में एक 4 सन्निकटन <math>O(n \log{n})</math> (अधिक सामान्यतः, | |||
* समय में 3 सन्निकटन <math>O(n^4)</math>; | * समय में 3 सन्निकटन <math>O(n^4)</math>; | ||
* समय में 1.75 सन्निकटन <math>O(n^5)</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> बाद वाला सन्निकटन [[गिलोटिन विभाजन]] नामक समस्या के प्रतिबंधित संस्करण का उपयोग करता है, जिसमें कट '''गिलोटिन कट्स''' (एज-टू-एज कट) की सही श्रंखला होनी चाहिए। | ||
* | * त्रुटिहीन गिलोटिन कट का उपयोग करते हुए कई [[बहुपद-समय सन्निकटन योजना]]एं होती है।<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 आयतों की किसी भी अधिकतम | * यदि बड़ा बहुभुज एक आयत है, तो n आयतों की किसी भी अधिकतम क्रम बद्धता में, सभी छिद्र आयत होते हैं, और उनकी संख्या अधिक से अधिक होती है <math>n - \lceil 2 \sqrt{n} - 1\rceil</math>, और यह घन होता है। | ||
* यदि बड़ा बहुभुज T प्रतिवर्ती शीर्षों वाला एक सरलरेखीय बहुभुज है, तो n आयतों की किसी भी अधिकतम | * यदि बड़ा बहुभुज 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'' भुजाएँ हैं, या अधिकतम ''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> | ||
=== रिक्त स्थान की संख्या कम करना === | === रिक्त स्थान की संख्या कम करना === | ||
मूल बहुभुज में पहले से ही कुछ | |||