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

From Vigyanwiki
m (15 revisions imported from alpha:बहुभुज_त्रिभुज)
(No difference)

Revision as of 10:57, 16 May 2023

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

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

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

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

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

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

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

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

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

,

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

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

कान कतरन विधि

बहुभुज कान

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

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

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

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

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

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

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

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

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

अभिकलनात्मक जटिलता

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

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

  • दोनों त्रिकोणासन समस्याएँ त्रिभुज (ज्यामिति) का विशेष स्थिति और बहुभुज विभाजन का विशेष स्थिति है।
  • न्यूनतम-भार त्रिभुज एक त्रिभुज है जिसमें लक्ष्य कुल किनारे की लंबाई को कम करना है।
  • बिंदु-सेट त्रिभुज बिंदुओं के समूह के उत्तल पतवार का बहुभुज त्रिभुज है। डेलौने त्रिकोणीयकरण बिंदुओं के सेट के आधार पर त्रिभुज बनाने की एक और विधि है।
  • असोसिएहेड्रोन बहुशीर्षक है जिसके कोने उत्तल बहुभुज के त्रिभुजों के अनुरूप होते हैं।
  • बहुभुज त्रिभुज आवरण, जिसमें त्रिभुज अधिव्यापन हो सकते हैं।
  • उत्तल नियमित बहुभुजों द्वारा यूक्लिडियन झुकाव, जहां लक्ष्य पूरे विमान को पूर्व-निर्दिष्ट आकृतियों के बहुभुजों से आवरण करना है।

यह भी देखें

संदर्भ

  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


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

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

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बहुभुज_त्रिभुज&oldid=155451’