बहुभुज त्रिभुज: Difference between revisions

Revision as of 00:16, 12 May 2023

बहुभुज त्रिभुज

कम्प्यूटेशनल ज्यामिति में, बहुभुज त्रिभुज बहुभुज क्षेत्र (सरल बहुभुज) $P$ का त्रिकोण के सेट में बहुभुज विभाजन है। ^[1] अर्थात, जोड़ीदार गैर-प्रतिच्छेदी अंदरूनी हिस्सों वाले त्रिकोणों का सेट खोजना जिसका संघ (सेट सिद्धांत) $P$ है।

त्रिभुजों को प्लानर सीधी-रेखा ग्राफ़ के विशेष मामलों के रूप में देखा जा सकता है। जब कोई छिद्र या अतिरिक्त बिंदु नहीं होते हैं, तो त्रिकोणासन बाहरी समतलीय ग्राफ बनाते हैं।

अतिरिक्त शीर्षों के बिना बहुभुज त्रिभुज

समय के साथ, बहुभुज को त्रिकोणित करने के लिए कई एल्गोरिदम प्रस्तावित किए गए हैं।

विशेष स्थितियां

उत्तल क्षेत्र सातकोणक (7-पक्षीय उत्तल बहुभुज) के लिए 42 संभावित त्रिभुज। यह संख्या 5वीं कैटलन संख्या द्वारा दी गई है।

किसी भी उत्तल बहुभुज को रेखीय समय में पंखे त्रिभुज में त्रिकोणित करना तुच्छ है, शीर्ष से अन्य सभी गैर-निकटतम पड़ोसी कोने में विकर्ण जोड़कर।

उत्तल बहुभुज |n-गॉन को गैर-प्रतिच्छेदित विकर्णों द्वारा त्रिकोणित करने के विधियों की कुल संख्या (n−2)nd कैटलन संख्या है, जो बराबर है

{\frac {n(n+1)...(2n-4)}{(n-2)!}}

,

लियोनहार्ड यूलर द्वारा खोजा गया सूत्र।^[2]

मोनोटोन बहुभुज को रैखिक समय में या तो A.फोरनियर और D. Y. मोंटूनो^[3] के एल्गोरिदम या गॉडफ्राइड टूसेंट के एल्गोरिदम के साथ त्रिकोणीय किया जा सकता है।^[4]

कान कतरन विधि

बहुभुज कान

साधारण बहुभुज को त्रिकोणित करने का तरीका दो कानों के प्रमेय पर आधारित है, इस तथ्य के रूप में कि छेद के बिना कम से कम 4 कोने वाले किसी भी साधारण बहुभुज में कम से कम दो 'कान (गणित)' होते हैं, जो त्रिभुज होते हैं जिनके दो किनारे किनारे होते हैं। बहुभुज का और तीसरा पूरी तरह से उसके अंदर।^[5] एल्गोरिथम में ऐसे कान को ढूंढना शामिल है, इसे बहुभुज से हटा दिया जाता है (जिसके परिणामस्वरूप नया बहुभुज होता है जो अभी भी शर्तों को पूरा करता है) और तब तक दोहराता है जब तक कि केवल त्रिकोण शेष न हो।

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

मोनोटोन बहुभुज त्रिभुज

बहुभुज को मोनोटोन बहुभुजों में तोड़ना

रेखा के संबंध में साधारण बहुभुज मोनोटोन है $L$ , यदि कोई रेखा ओर्थोगोनल है $L$ बहुभुज को अधिकतम दो बार प्रतिच्छेद करता है। मोनोटोन बहुभुज को दो मोनोटोन श्रृंखलाओं में विभाजित किया जा सकता है। बहुभुज जो y-अक्ष के संबंध में मोनोटोन है, y-मोनोटोन कहलाता है। के साथ मोनोटोन बहुभुज $n$ शीर्षों को त्रिभुजित किया जा सकता है $O(n)$ समय। किसी दिए गए बहुभुज को y-मोनोटोन मानते हुए, लालची एल्गोरिथ्म बहुभुज की श्रृंखला पर ऊपर से नीचे तक चलने से शुरू होता है, जब भी संभव हो विकर्ण जोड़ते हैं।^[1]यह देखना आसान है कि एल्गोरिथ्म को किसी भी मोनोटोन बहुभुज पर लागू किया जा सकता है।

गैर-एकरस बहुभुज का त्रिकोणीकरण

यदि कोई बहुभुज मोनोटोन नहीं है, तो इसे मोनोटोन सबपॉलीगॉन में विभाजित किया जा सकता है $O(n log n)$ स्वीप लाइन एल्गोरिथ्म का उपयोग करते हुए समय|स्वीप-लाइन दृष्टिकोण। एल्गोरिदम को बहुभुज को सरल होने की आवश्यकता नहीं होती है, इस प्रकार इसे बहुभुजों पर छेद के साथ लागू किया जा सकता है। आम तौर पर, यह एल्गोरिदम प्लानर उपखंड को त्रिकोणित कर सकता है $n$ शिखरों में $O(n log n)$ समय का उपयोग करना $O(n)$ अंतरिक्ष।^[1]

त्रिभुज का दोहरा ग्राफ

उपयोगी ग्राफ़ जो अक्सर बहुभुज के त्रिभुज से जुड़ा होता है $P$ दोहरा ग्राफ है। त्रिभुज दिया $T P$ का $P$ , ग्राफ को परिभाषित करता है $G (T P)$ उस ग्राफ के रूप में जिसका शीर्ष समुच्चय के त्रिभुज हैं $T P$ , दो शीर्ष (त्रिकोण) आसन्न हैं यदि और केवल यदि वे विकर्ण साझा करते हैं। इसका अवलोकन करना आसान है $G (T P)$ अधिकतम डिग्री 3 के साथ वृक्ष (ग्राफ सिद्धांत) है।

कम्प्यूटेशनल जटिलता

1988 तक, क्या साधारण बहुभुज की तुलना में तेजी से त्रिकोणित किया जा सकता है $O(n log n)$ कम्प्यूटेशनल ज्यामिति में समय खुली समस्या थी।^[1]फिर, Tarjan & Van Wyk (1988) की खोज की $O(n log log n)$ त्रिकोणासन के लिए समय एल्गोरिथ्म,^[7] बाद में द्वारा सरलीकृत किया गया Kirkpatrick, Klawe & Tarjan (1992).^[8] जटिलता के साथ कई बेहतर तरीके $O(n log * n)$ (व्यवहार में, रैखिक समय से अप्रभेद्य) का पालन किया।^[9]^[10]^[11] बर्नार्ड चाज़ेल ने 1991 में दिखाया कि किसी भी साधारण बहुभुज को रैखिक समय में त्रिभुजित किया जा सकता है, हालांकि प्रस्तावित एल्गोरिथम बहुत जटिल है।^[12] रैखिक अपेक्षित समय के साथ सरल यादृच्छिक एल्गोरिथम भी जाना जाता है।^[13] सेडेल के अपघटन एल्गोरिदम और चाज़ेल की त्रिभुज विधि पर विस्तार से चर्चा की गई है Li & Klette (2011).^[14] के त्रिकोणासन की समय जटिलता $n$ छेद वाले वर्टेक्स बहुभुज में है $Ω(n log n)$ निचली सीमा, संगणना के बीजगणितीय संगणना ट्री मॉडल में।^[1]गतिशील प्रोग्रामिंग का उपयोग करके बहुपद समय में साधारण बहुभुज के अलग-अलग त्रिभुजों की संख्या की गणना करना संभव है, और (इस गिनती एल्गोरिथ्म के आधार पर) बहुपद समय में असतत समान वितरण त्रिभुज उत्पन्न करने के लिए।^[15] हालांकि, छेद वाले बहुभुज के त्रिभुजों की गिनती ♯P-पूर्ण|#P-पूर्ण है, जिससे यह संभावना नहीं है कि यह बहुपद समय में किया जा सकता है।^[16]

यह भी देखें

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), "3: Polygon Triangulation", Computational Geometry (2nd ed.), Springer-Verlag, pp. 45–61, ISBN 3-540-65620-0{{citation}}: CS1 maint: multiple names: authors list (link)
↑ Pickover, Clifford A. (2009), The Math Book, Sterling, p. 184
↑ Fournier, Alain; Montuno, Delfin Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301, S2CID 33344266
↑ Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons", Pattern Recognition Letters, 2 (3): 155–158, Bibcode:1984PaReL...2..155T, doi:10.1016/0167-8655(84)90039-4
↑ Meisters, Gary Hosler (1975), "Polygons have ears", American Mathematical Monthly, 82 (6): 648–651, doi:10.2307/2319703, JSTOR 2319703
↑ ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried T. (1993), "Slicing an ear using prune-and-search", Pattern Recognition Letters, 14 (9): 719–722, Bibcode:1993PaReL..14..719E, doi:10.1016/0167-8655(93)90141-y
↑ Tarjan, Robert E.; Van Wyk, Christopher J. (1988), "An O(n log log n)-time algorithm for triangulating a simple polygon", SIAM Journal on Computing, 17 (1): 143–178, CiteSeerX 10.1.1.186.5949, doi:10.1137/0217010, MR 0925194
↑ Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E. (1992), "Polygon triangulation in O(n log log n) time with simple data structures", Discrete & Computational Geometry, 7 (4): 329–346, doi:10.1007/BF02187846, MR 1148949
↑ Clarkson, Kenneth L.; Tarjan, Robert; van Wyk, Christopher J. (1989), "A fast Las Vegas algorithm for triangulating a simple polygon", Discrete & Computational Geometry, 4 (5): 423–432, doi:10.1007/BF02187741
↑ Seidel, Raimund (1991), "A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons", Computational Geometry, 1: 51–64, doi:10.1016/0925-7721(91)90012-4
↑ Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E. (1992), "Randomized parallel algorithms for trapezoidal diagrams", International Journal of Computational Geometry & Applications, 2 (2): 117–133, doi:10.1142/S0218195992000081, MR 1168952
↑ Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 6 (3): 485–524, doi:10.1007/BF02574703, ISSN 0179-5376
↑ Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 26 (2): 245–265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376
↑ Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5
↑ Epstein, Peter; Sack, Jörg-Rüdiger (1994), "Generating triangulations at random", ACM Transactions on Modeling and Computer Simulation, 4 (3): 267–278, doi:10.1145/189443.189446, S2CID 14039662
↑ Eppstein, David (2019), "Counting polygon triangulations is hard", Proc. 35nd Int. Symp. Computational Geometry, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl, pp. 33:1–33:17, arXiv:1903.04737, doi:10.4230/LIPIcs.SoCG.2019.33, S2CID 75136891

इस पेज में लापता आंतरिक लिंक की सूची

साधारण बहुभुज
त्रिभुज
आउटरप्लानर ग्राफ
प्लानर स्ट्रेट-लाइन ग्राफ
प्रशंसक त्रिकोण
रैखिक समय
दो कान प्रमेय
लालची एल्गोरिदम
निम्न परिबंध
गणना वृक्ष
त्रिकोणासन (ज्यामिति)
न्यूनतम वजन त्रिकोण
उत्तल नियमित बहुभुजों द्वारा यूक्लिडियन टाइलिंग
Delaunay त्रिभुज

बाहरी संबंध

Demo as Flash swf, A Sweep Line algorithm.
Song Ho's explanation of the OpenGL GLU tesselator

[bkos-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), "3: Polygon Triangulation", Computational Geometry (2nd ed.), Springer-Verlag, pp. 45–61, ISBN 3-540-65620-0{{citation}}: CS1 maint: multiple names: authors list (link)

[2] Pickover, Clifford A. (2009), The Math Book, Sterling, p. 184

[3] Fournier, Alain; Montuno, Delfin Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301, S2CID 33344266

[4] Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons", Pattern Recognition Letters, 2 (3): 155–158, Bibcode:1984PaReL...2..155T, doi:10.1016/0167-8655(84)90039-4

[5] Meisters, Gary Hosler (1975), "Polygons have ears", American Mathematical Monthly, 82 (6): 648–651, doi:10.2307/2319703, JSTOR 2319703

[6] ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried T. (1993), "Slicing an ear using prune-and-search", Pattern Recognition Letters, 14 (9): 719–722, Bibcode:1993PaReL..14..719E, doi:10.1016/0167-8655(93)90141-y

[7] Tarjan, Robert E.; Van Wyk, Christopher J. (1988), "An O(n log log n)-time algorithm for triangulating a simple polygon", SIAM Journal on Computing, 17 (1): 143–178, CiteSeerX 10.1.1.186.5949, doi:10.1137/0217010, MR 0925194

[8] Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E. (1992), "Polygon triangulation in O(n log log n) time with simple data structures", Discrete & Computational Geometry, 7 (4): 329–346, doi:10.1007/BF02187846, MR 1148949

[9] Clarkson, Kenneth L.; Tarjan, Robert; van Wyk, Christopher J. (1989), "A fast Las Vegas algorithm for triangulating a simple polygon", Discrete & Computational Geometry, 4 (5): 423–432, doi:10.1007/BF02187741

[10] Seidel, Raimund (1991), "A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons", Computational Geometry, 1: 51–64, doi:10.1016/0925-7721(91)90012-4

[11] Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E. (1992), "Randomized parallel algorithms for trapezoidal diagrams", International Journal of Computational Geometry & Applications, 2 (2): 117–133, doi:10.1142/S0218195992000081, MR 1168952

[12] Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 6 (3): 485–524, doi:10.1007/BF02574703, ISSN 0179-5376

[13] Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 26 (2): 245–265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376

[14] Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5

[15] Epstein, Peter; Sack, Jörg-Rüdiger (1994), "Generating triangulations at random", ACM Transactions on Modeling and Computer Simulation, 4 (3): 267–278, doi:10.1145/189443.189446, S2CID 14039662

[16] Eppstein, David (2019), "Counting polygon triangulations is hard", Proc. 35nd Int. Symp. Computational Geometry, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl, pp. 33:1–33:17, arXiv:1903.04737, doi:10.4230/LIPIcs.SoCG.2019.33, S2CID 75136891

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

@@ Line 9: / Line 9: @@
 [[File:Polygon Triangulations (heptagon).svg|thumb|[[उत्तल क्षेत्र]] [[सातकोणक]] (7-पक्षीय उत्तल बहुभुज) के लिए 42 संभावित त्रिभुज। यह संख्या 5वीं [[कैटलन संख्या]] द्वारा दी गई है।]]किसी भी [[उत्तल बहुभुज]] को रेखीय समय में पंखे त्रिभुज में त्रिकोणित करना तुच्छ है,  शीर्ष से अन्य सभी गैर-निकटतम पड़ोसी कोने में विकर्ण जोड़कर।
-उत्तल बहुभुज|n-गॉन को गैर-प्रतिच्छेदित विकर्णों द्वारा त्रिकोणित करने के तरीकों की कुल संख्या (n−2)nd कैटलन संख्या है, जो बराबर है
+उत्तल बहुभुज |n-गॉन को गैर-प्रतिच्छेदित विकर्णों द्वारा त्रिकोणित करने के विधियों की कुल संख्या (n−2)nd कैटलन संख्या है, जो बराबर है
 :<math>\frac{n(n+1)...(2n-4)}{(n-2)!}</math>,
 [[लियोनहार्ड यूलर]] द्वारा खोजा गया  सूत्र।<ref>{{citation|author-link=Clifford Pickover|last=Pickover|first= Clifford A.|title=The Math Book|publisher= Sterling|year= 2009|page= 184}}</ref>
-एलेन फोरनियर|ए के एल्गोरिथम के साथ रैखिक समय में  [[मोनोटोन बहुभुज]] को त्रिकोणित किया जा सकता है। फोर्नियर और डी.वाई. मोंटूनो,<ref>{{citation
+[[मोनोटोन बहुभुज]] को रैखिक समय में या तो [[A.फोरनियर]] और D. Y. मोंटूनो<ref>{{citation
 | last1=Fournier | first1=Alain | author1-link=Alain Fournier
 | last2=Montuno |first2= Delfin Y.
@@ Line 22: / Line 23: @@
 | pages=153–174
 | issn=0730-0301
-| doi=10.1145/357337.357341|s2cid=33344266 }}</ref> या [[गॉडफ्राइड टूसेंट]] का एल्गोरिदम।<ref>{{citation
+| doi=10.1145/357337.357341|s2cid=33344266 }}</ref> के एल्गोरिदम या [[गॉडफ्राइड टूसेंट]] के एल्गोरिदम के साथ त्रिकोणीय किया जा सकता है।<ref>{{citation
 | first1=Godfried T. | last1=Toussaint
 | year=1984
@@ Line 32: / Line 33: @@
 | doi=10.1016/0167-8655(84)90039-4| bibcode=1984PaReL...2..155T
 }}</ref>

Anonymous

Search

बहुभुज त्रिभुज: Difference between revisions

Namespaces

More

Page actions

Revision as of 00:16, 12 May 2023

Contents

अतिरिक्त शीर्षों के बिना बहुभुज त्रिभुज

विशेष स्थितियां

कान कतरन विधि

मोनोटोन बहुभुज त्रिभुज

गैर-एकरस बहुभुज का त्रिकोणीकरण

त्रिभुज का दोहरा ग्राफ

कम्प्यूटेशनल जटिलता

संबंधित वस्तुएं और समस्याएं

यह भी देखें

संदर्भ

इस पेज में लापता आंतरिक लिंक की सूची

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बहुभुज त्रिभुज: Difference between revisions

Revision as of 00:16, 12 May 2023

अतिरिक्त शीर्षों के बिना बहुभुज त्रिभुज

विशेष स्थितियां

कान कतरन विधि

मोनोटोन बहुभुज त्रिभुज

गैर-एकरस बहुभुज का त्रिकोणीकरण

त्रिभुज का दोहरा ग्राफ

कम्प्यूटेशनल जटिलता

संबंधित वस्तुएं और समस्याएं

यह भी देखें

संदर्भ

इस पेज में लापता आंतरिक लिंक की सूची

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories