बहुभुज विभाजन: 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]

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

इस समुच्चयन में, बड़े बहुभुज में पहले से ही कुछ युग्‍मानूसार-असंबद्ध आयत सम्मलित होते हैं। उद्देश्य बहुसंख्यक विभाजन को आयतों में इस तरह सम्मलित किया है जैसे कि प्रत्येक मूल आयत खण्ड़ो में समाहित होता है, और इसके अधीन, "रिक्�

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 57: / Line 57: @@
 वीएलएसआई आर्टवर्क प्रोसेसिंग सिस्टम में, बहुधा एक बहुभुज क्षेत्र को दो क्षैतिज भुजाओ  के साथ ट्रैपेज़ोइड्स की न्यूनतम संख्या में विभाजित करने की आवश्यकता होती है। एक क्षैतिज भुजा वाले त्रिभुज को दो क्षैतिज भुजाओं वाला एक समलम्बाकार माना जाता है, जिनमें से एक विकृत होता है। एक छिद्र -मुक्त बहुभुज के साथ <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>
+यदि समलम्बाभ की संख्या कम से कम नहीं होनी चाहिए, तो समय पर चतुर्भुज पाया जा सकता है <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>
+यदि बहुभुज में छिद्र होते हैं, तो समस्या एनपी-पूर्ण है, किन्तु समय में 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>
+पिछली समस्याओं का सामान्यीकरण उन बहुभुजों में विभाजन करना होता है जिनकी ठीक ''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>
 == एक बहुभुज को उत्तल बहुभुजों में विभाजित करें ==
 उत्तल बहुभुजों में एक सामान्य बहुभुज का विभाजन करते समय, कई उद्देश्यों का अध्ययन किया गया है।
@@ Line 84: / Line 84: @@
 == अधिक सामान्य घटक आकार ==
-खण्ड़ो  के अधिक सामान्य आकार का अध्ययन किया गया है, जिनमें सम्मलित हैं: सर्पिल आकार, स्टार बहुभुज और [[मोनोटोन बहुभुज]]। <ref name="Keil2000" /> एक सर्वेक्षण के लिए [देखें।
+खण्ड़ो के अधिक सामान्य आकार का अध्ययन किया गया है, जिनमें सम्मलित हैं: सर्पिल आकार, स्टार बहुभुज और [[मोनोटोन बहुभुज]]। <ref name="Keil2000" /> एक सर्वेक्षण के लिए [देखें।
 == यह भी देखें ==
@@ Line 97: / Line 97: @@
 ==संदर्भ==
 {{reflist}}
-[[Category: कम्प्यूटेशनल ज्यामिति]] [[Category: बहुभुज]] [[Category: पैकिंग की समस्या]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1 English-language sources (en)]]
-[[Category: Machine Translated Page]]
 [[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