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

Latest revision as of 16:26, 24 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)$ , बहुभुज त्रिभुज एल्गोरिथम के उपोत्पाद के रूप में होता है ।^[14]

यदि बहुभुज में छिद्र होते हैं, तो समस्या एनपी-पूर्ण है, किन्तु समय में 3-सन्निकटन के रूप मे पाया जा सकता है $O(n\log n)$ .^[13]

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

एक चतुर्भुज या चतुष्कोण चतुर्भुज में एक विभाजन है।

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

स्टेनर बिंदुओं के साथ छिद्र -मुक्त बहुभुजों के चतुष्कोणों के लिए रैखिक-समय एल्गोरिदम हैं, किन्तु सबसे छोटा विभाजन खोजने की गारंटी नहीं है।^[15]^[16]

एक बहुभुज को m-gons में विभाजित करें

पिछली समस्याओं का सामान्यीकरण उन बहुभुजों में विभाजन करना होता है जिनकी ठीक m भुजाएँ हैं, या अधिकतम m भुजाएँ हैं। यहाँ उद्देश्य कुल कोणों की लंबाई को कम करना है। इस समस्या को n और m में समय बहुपद में हल किया जा सकता है।^[17]^[18]

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

उत्तल बहुभुजों में एक सामान्य बहुभुज का विभाजन करते समय, कई उद्देश्यों का अध्ययन किया गया है।

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

इष्टतम उत्तल विभाजन समस्या एक गैर-उत्तल बहुभुज को यथासंभव कुछ उत्तल बहुभुजों में विभाजित करता है, केवल प्रारंभिक बहुभुज के शीर्ष का उपयोग करना। इस समस्या के लिए त्रुटिहीन और अनुमानित एल्गोरिदम हैं।^[19]

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

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

क्षेत्र और परिधि को बराबर करना

निष्पक्ष बहुभुज विभाजन समस्या ^[20] एक (उत्तल) बहुभुज को एक समान परिधि और समान क्षेत्रो के साथ (उत्तल) खण्ड़ो में विभाजित करना है (यह निष्पक्ष केक काटने का एक विशेष स्थिति होती है)। किसी भी उत्तल बहुभुज को ठीक 1/n के क्षेत्र वाले उत्तल स्थान के किसी भी संख्या 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.

[Keil2000-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.

[Eppstein2009-2] 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.

[Slaw2013-3] Realz Slaw. "वर्गों के साथ एक ओर्थोगोनल बहुभुज टाइलिंग". CS stack exchange. Retrieved 19 October 2015.

[:0-4] 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.

[:1-5] 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.

[:3-6] 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.

[7] 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.

[8] 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.

[:2-9] 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.

[10] 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.

[11] 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.

[:4-12] 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.

[Asano1986-13] 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.

[Chazelle1991-14] Chazelle, Bernard (2007). "रेखीय समय में एक साधारण बहुभुज को त्रिभुजित करना". Discrete & Computational Geometry. 6 (3): 485–524. doi:10.1007/bf02574703.

[Everett1992-15] H. Everett; W. Lenhart; M. Overmars; T. Shermer; J. Urrutia. (1992). "बहुभुजों का कड़ाई से उत्तल चतुर्भुज". Proc. 4th Canad. Conf. Comput. Geom. pp. 77–83.

[Ramaswami1998-16] Ramaswami, Suneeta; Ramos, Pedro; Toussaint, Godfried (1998). "त्रिभुजों को चतुर्भुजों में बदलना". Computational Geometry. 9 (4): 257. doi:10.1016/s0925-7721(97)00019-9.

[Lingas1987-17] Lingas, Andrzej; Levcopoulos, Christos; Sack, Jörg (1987). "बहुभुजों की न्यूनतम लंबाई वाले विभाजनों के लिए एल्गोरिदम". BIT. 27 (4): 474. doi:10.1007/bf01937272. S2CID 30936524.

[Levcopoulos1989-18] Levcopoulos, Christos; Lingas, Andrzej; Sack, Jörg-R. (1989). "इष्टतम बाइनरी सर्च ट्री और न्यूनतम वजन त्रिकोणासन समस्याओं के लिए ह्यूरिस्टिक्स". Theoretical Computer Science. 66 (2): 181. doi:10.1016/0304-3975(89)90134-5.

[19] 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.

[20] 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.

[21] 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.

[22] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

@@ Line 1: / Line 1: @@
 {{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>{{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/>
-<nowiki>*</nowiki>पैटर्न पहचान तकनीक किसी वस्तु का वर्णन, पहचान या वर्गीकरण करने के लिए उससे जानकारी निकालती है। एक सामान्य बहुभुज वस्तु को पहचानने के लिए एक स्थापित रणनीति यह होती है कि इसे सरल घटकों मे विघटित किया जाए, फिर घटकों और उनके अंतर्संबंधों की पहचान की जाए और इस जानकारी का उपयोग वस्तु के आकार को निर्धारित करने के लिए किया जाए।
+<nowiki>*</nowiki>अभिरचना पहचान तकनीक किसी वस्तु का वर्णन, पहचान या वर्गीकरण करने के लिए उससे जानकारी निकालती है। एक सामान्य बहुसंख्यक वस्तु को पहचानने के लिए एक स्थापित योजना यह होती है कि इसे सरल घटकों मे विघटित किया जाए, फिर घटकों और उनके अंतर्संबंधों की पहचान की जाए और इस जानकारी का उपयोग वस्तु के आकार को निर्धारित करने के लिए किया जाए।
-* [[वीएलएसआई]] कलाकृति डाटा प्रोसेसिंग में, लेआउट को बहुभुज के रूप में दर्शाया जाता है, और इलेक्ट्रॉन-बीम लिथोग्राफी की तैयारी के लिए एक दृष्टिकोण इन बहुभुज क्षेत्रों को मौलिक आंकड़ों में विघटित करना है। रूटिंग क्षेत्र को चैनलों में विभाजित करने की प्रक्रिया में बहुभुज अपघटन का भी उपयोग किया जाता है।
+* [[वीएलएसआई]] प्रोजेक्ट डाटा प्रसंस्करण में, लेआउट को बहुभुज के रूप में दर्शाया जाता है, और इलेक्ट्रॉन-बीम लिथोग्राफी की तैयारी के लिए इन बहुरूपताओ को बहुभुज क्षेत्रों को मौलिक आंकड़ों में विघटित करना होता है। परिच्छेदन क्षेत्र को चैनलों में विभाजित करने की प्रक्रिया में बहुभुज अपघटन का भी उपयोग किया जाता है।
-* कम्प्यूटेशनल ज्यामिति में, सामान्य बहुभुजों पर समस्याओं के लिए एल्गोरिदम अधिकांशतः प्रतिबंधित प्रकार के बहुभुज जैसे कि उत्तल या तारे के आकार के लिए अधिक जटिल होते हैं। पॉइंट-इन-पॉलीगॉन समस्या इसका एक उदाहरण है। सामान्य बहुभुजों पर इस प्रकार की कुछ समस्याओं को हल करने की एक रणनीति है कि बहुभुज को सरल घटक भागों में विघटित किया जाए, एक विशेष एल्गोरिथम का उपयोग करके प्रत्येक घटक पर समस्या को हल किया जाए, और फिर आंशिक समाधानों को संयोजित किया जाए।
+* कम्प्यूटेशनल ज्यामिति में, सामान्य बहुसंख्यक समस्याओं के लिए एल्गोरिदम अधिकांशतः प्रतिबंधित प्रकार के बहुभुज जैसे कि उत्तल या तारे के आकार के लिए अधिक जटिल होते हैं। पॉइंट-इन- बहुभुज समस्या इसका एक उदाहरण है। सामान्य बहुभुजों पर इस प्रकार की कुछ समस्याओं को हल करने की एक रणनीति है कि बहुभुज को सरल घटक भागों में विघटित किया जाए, एक विशेष एल्गोरिथम का उपयोग करके प्रत्येक घटक पर समस्या को हल किया जाए, और फिर आंशिक समाधानों को संयोजित किया जाए।
-* अन्य अनुप्रयोगों में डेटा कम्प्रेशन [[डेटाबेस सिस्टम|डेटाबेस प्रणाली]],  [[ मूर्ति प्रोद्योगिकी |प्रतिबिंब प्रक्रमण]]   और [[ कंप्यूटर चित्रलेख | कंप्यूटर चित्रलेख]] सम्मलित होते हैं।
+* अन्य अनुप्रयोगों में डेटा कम्प्रेशन [[डेटाबेस सिस्टम|डेटाबेस प्रणाली]],  [[ मूर्ति प्रोद्योगिकी |प्रतिबिंब प्रक्रमण]] और [[ कंप्यूटर चित्रलेख |कंप्यूटर चित्रलेख]] सम्मलित होते हैं।
 == एक बहुभुज को त्रिभुजों में विभाजित करना ==
 {{Main|बहुभुज त्रिभुज
-|न्यूनतम वजन त्रिकोण}}
+|न्यूनतम भार त्रिकोण}}
-मूख्य रुप से अध्ययन की गई बहुभुज विभाजन समस्या त्रिकोणों की एक छोटी संख्या में विभाजन होती है, जिसे त्रिकोणासन भी कहा जाता है। एक छिद्र-मुक्त बहुभुज के साथ <math>n</math> कोने होते है, और समय में त्रिभुज की गणना की जा सकती है <math>\Theta(n)</math> छिद्र वाले बहुभुज के लिए, निम्न सीमा होती है <math>\Omega(n \log n)</math>।
+मूख्य रुप से अध्ययन की गई बहुभुज विभाजन समस्या त्रिकोणों की एक छोटी संख्या में विभाजन होत है, जिसे '''त्रिकोणासन''' भी कहा जाता है। एक छिद्र-मुक्त बहुभुज के साथ <math>n</math> कोने होते है, एक त्रिभुज की गणना समय मे की जा सकती है <math>\Theta(n)</math>। छिद्र वाले बहुभुज के लिए, निम्न सीमा होती है <math>\Omega(n \log n)</math>।
-एक सम्बद्धित समस्या न्यूनतम कुल छोर की लंबाई वाले त्रिकोणों में विभाजन करती है, जिसे न्यूनतम-भार त्रिकोणासन भी कहा जाता है।
+एक सम्बद्धित समस्या न्यूनतम कुल छोर की लंबाई वाले त्रिकोणों में विभाजन करती है, जिसे '''न्यूनतम-भार त्रिकोणासन''' भी कहा जाता है।
 == एक बहुभुज को छद्म-त्रिकोणों में विभाजित करना ==
-{{Main| छद्मत्रिभुज § स्यूडोट्राएंगुलेशन}}
+{{Main| छद्मत्रिभुज § छद्मत्रिकोण}}
-समस्या के समान दो रूपों का अध्ययन उस स्थिति के लिए किया गया था जिसमें टुकड़े छद्म त्रिभुज होने चाहिए - बहुभुज जो त्रिभुजों की तरह तीन उत्तल शिखर होते हैं। भिन्नरूप होते हैं: सबसे छोटी संख्या में छद्मत्रिभुजों का विभाजन, और न्यूनतम कुल छोर की लंबाई के साथ [[छद्मत्रिकोण|छद्मत्रिकोणों]] का विभाजन होता है ।
+समस्या के उन्हीं दो प्रकारों का अध्ययन उस स्थिति के लिए किया गया था जिसमें टुकड़े छद्म त्रिभुज होने चाहिए - बहुभुज जो त्रिभुजों की तरह तीन उत्तल शिखर होते हैं। भिन्नरूप होते हैं: सबसे छोटी संख्या में छद्मत्रिभुजों का विभाजन, और न्यूनतम कुल कोणों की लंबाई के साथ [[छद्मत्रिकोण|छद्मत्रिकोणों]] का विभाजन होता है ।
 == एक आयताकार बहुभुज को आयतों में विभाजित करना ==
-बहुभुज विभाजन समस्याओं का एक विशेष उपकुल तब उत्पन्न होता है जब बड़ा बहुभुज सरलरेखीय बहुभुज होता है (जिसे: ओर्थोगोनल बहुभुज भी कहा जाता है)। इस स्थिति में, विचार करने के लिए सबसे महत्वपूर्ण घटक आकार आयत होता है।<ref name=Keil2000/>
+बहुविभाजित समस्याओं की एक विशेष उप-श्रेणी तब उत्पन्न होती  है जब बड़ा बहुभुज '''सरल रेखीय बहुभुज''' होता है (जिसे: ओर्थोगोनल बहुभुज भी कहा जाता है)। इस स्थिति में, विचार करने के लिए सबसे महत्वपूर्ण घटक आकार आयत होता है।<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=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=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>
+एक आयताकार बहुभुज को वर्गों की सबसे छोटी संख्या में विभाजित करने की समस्या (स्वैच्छिक आयतों के विपरीत) एनपी- ठोस होता है।<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> इस समस्या की रन-टाइम जटिलता महत्वपूर्ण रूप से इस बात पर निर्भर करती है कि कच्चे बहुभुज में छेद होने की अनुमति है या नहीं।
+कुछ अनुप्रयोगों में, कर्त की कुल लंबाई को कम करना अधिक महत्वपूर्ण होता है (उदाहरण के लिए विभाजन करने की लागत को कम करने के लिए, या धूल की मात्रा को कम करने के लिए)। इस समस्या को न्यूनतम कोणों-लंबाई का आयताकार विभाजन कहा जाता है। 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> उस मामले के लिए जिसमें सभी छेद एकल बिंदु हैं, कई स्थिर-कारक सन्निकटन विकसित किए गए हैं:
+यदि अपरिष्कृ बहुभुज में छिद्र हो सकते हैं,  यदि वे  विकृत छिद्र (अर्थात , एकल बिंदु) हों, तो समस्या एनपी-हार्ड होती है। इसे [[प्लानर सैट|समतलीय सैट]] से घटाकर सिद्ध किया जा सकता है।<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> उस स्थिति के लिए जिसमें सभी छिद्र एकल बिंदु होते हैं, कई स्थिर-कारक सन्निकटन विकसित किए गए हैं:
-* ए (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>
+* A (3+sqrt(3)) समय में सन्निकटन <math>O(n^2)</math>;<ref name=":3" />
-* समय में एक 4 सन्निकटन <math>O(n \log{n})</math> (अधिक सामान्यतः, डी आयामों में, यह एक है <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>
+*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>
 * समय में 3 सन्निकटन <math>O(n^4)</math>;
-* समय में 1.75 सन्निकटन <math>O(n^5)</math> (अधिक सामान्यतः, डी आयामों में, यह एक है <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>{{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>
+इस समुच्चयन में, बड़े बहुभुज में पहले से ही कुछ युग्‍मानूसार-असंबद्ध आयत सम्मलित होते हैं। उद्देश्य बहुसंख्यक विभाजन को आयतों में इस तरह सम्मलित किया है  जैसे कि प्रत्येक मूल आयत खण्ड़ो  में समाहित होता है, और इसके अधीन, "रिक्त स्थान"  की संख्या (टुकड़े जिनमें मूल आयत नहीं होते है) जितना संभव हो उतना छोटा है। निम्नलिखित परिणाम ज्ञात हैं:<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>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>
+यदि समलम्बाभ की संख्या कम से कम नहीं होनी चाहिए, तो समय पर चतुर्भुज पाया जा सकता है <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 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>
+इष्टतम उत्तल विभाजन समस्या एक गैर-[[उत्तल बहुभुज]] को यथासंभव कुछ उत्तल बहुभुजों में विभाजित करता  है, केवल प्रारंभिक बहुभुज के शीर्ष का उपयोग करना। इस समस्या के लिए त्रुटिहीन और अनुमानित एल्गोरिदम हैं।<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>
+इस समस्या का एक सामान्यीकरण तब होता है जब क्षेत्र और परिधि के उपायों को क्रमशः तत्व पर और बहुभुज की सीमा पर माप के साथ बदल दिया जाता है। 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>
-=== क्षेत्र और परिधि को बराबर करना ===
+किसी भी संख्या के उपायों को संभालने के लिए और सामान्यीकरण किया जाता है।
-निष्पक्ष बहुभुज विभाजन समस्या<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> एक (उत्तल) बहुभुज को (उत्तल) टुकड़ों में एक समान परिधि और समान क्षेत्र के साथ विभाजित करना है (यह निष्पक्ष केक काटने का एक विशेष मामला है)। किसी भी उत्तल बहुभुज को उत्तल टुकड़ों की किसी भी संख्या n में ठीक 1/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>
-किसी भी संख्या के उपायों को संभालने के लिए एक और सामान्यीकरण है।
 == अधिक सामान्य घटक आकार ==
-टुकड़ों के अधिक सामान्य आकार का अध्ययन किया गया है, जिनमें सम्मलित हैं: सर्पिल आकार, स्टार बहुभुज और [[मोनोटोन बहुभुज]]। देखना <ref name="Keil2000" />एक सर्वेक्षण के लिए।
+खण्ड़ो के अधिक सामान्य आकार का अध्ययन किया गया है, जिनमें सम्मलित हैं: सर्पिल आकार, स्टार बहुभुज और [[मोनोटोन बहुभुज]]। <ref name="Keil2000" /> एक सर्वेक्षण के लिए [देखें।
 == यह भी देखें ==
-* पॉलीगॉन कवरिंग - एक संबंधित समस्या जिसमें टुकड़ों को ओवरलैप करने की अनुमति दी जाती है।
+* बहुभुज कवरिंग - एक संबंधित समस्या जिसमें खण्ड़ो  को ओवरलैप करने की अनुमति दी जाती है।
-* पैकिंग समस्याएँ - एक संबंधित समस्या जिसमें टुकड़ों को पूरी बड़ी वस्तु के भीतर फिट होना पड़ता है लेकिन उसे पूरी तरह से ढकना नहीं पड़ता।
+* पैकिंग समस्याएँ - एक संबंधित समस्या जिसमें खण्ड़ो  को पूरी बड़ी वस्तु के भीतर फिट होना पड़ता है किन्तु  उसे पूरी तरह से ढकना नहीं पड़ता।
 * [[उत्तल नियमित बहुभुजों द्वारा यूक्लिडियन टाइलिंग]] - पूरे समतल को सरल बहुभुजों में विभाजित करने की समस्या जैसे कि [[आयतों के साथ टाइलिंग]]।
 * वर्ग का वर्ग बनाना - केवल अन्य अभिन्न वर्गों का उपयोग करके एक अभिन्न वर्ग को विभाजित करने की समस्या।
 * [[अंतरिक्ष विभाजन]]
-* [[टाइलिंग पहेली]] - दिए गए कई टुकड़ों को दिए गए बड़े बहुभुज में पैक करने की पहेली।
+* [[टाइलिंग पहेली]] - दिए गए कई खण्ड़ो  को दिए गए बड़े बहुभुज में पैक करने की पहेली।
 * गिलोटिन विभाजन
 ==संदर्भ==
 {{reflist}}
-[[Category: कम्प्यूटेशनल ज्यामिति]] [[Category: बहुभुज]] [[Category: पैकिंग की समस्या]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1 English-language sources (en)]]
 [[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:बहुभुज]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 16:26, 24 May 2023

Contents

अनुप्रयोग

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

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

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

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

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

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

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

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

एक बहुभुज को m-gons में विभाजित करें

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

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

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

क्षेत्र और परिधि को बराबर करना

अधिक सामान्य घटक आकार

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 16:26, 24 May 2023

अनुप्रयोग

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

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

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

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

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

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

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

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

एक बहुभुज को m-gons में विभाजित करें

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

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

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

क्षेत्र और परिधि को बराबर करना

अधिक सामान्य घटक आकार

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories