बिंदु-सेट त्रिभुज

बिंदुओं के समूह का त्रिभुज ${\mathcal {P}}$ यूक्लिडियन अंतरिक्ष में $\mathbb {R} ^{d}$ एक साधारण परिसर है जो उत्तल हल को कवर करता है ${\mathcal {P}}$, और जिनके शिखर संबंधित हैं ${\mathcal {P}}$. विमान में (ज्यामिति) (जब ${\mathcal {P}}$ में बिंदुओं का एक समूह है $\mathbb {R} ^{2}$), त्रिभुज, उनके किनारों और शीर्षों सहित, त्रिभुजों से बने होते हैं। कुछ लेखकों की आवश्यकता है कि के सभी बिंदु ${\mathcal {P}}$ इसके त्रिकोणासन के शीर्ष हैं। इस मामले में, बिंदुओं के एक सेट का त्रिभुज ${\mathcal {P}}$ विमान में वैकल्पिक रूप से बिंदुओं के बीच गैर-क्रॉसिंग किनारों के अधिकतम सेट के रूप में परिभाषित किया जा सकता है ${\mathcal {P}}$. समतल में, त्रिभुज तलीय सीधी-रेखा ग्राफ़|तलीय सीधी-रेखा ग्राफ़ के विशेष मामले हैं।

एक विशेष रूप से दिलचस्प प्रकार का त्रिकोण डेलाउने त्रिभुज है। वे वोरोनोई आरेख के दोहरे पॉलीटॉप हैं। बिंदुओं के एक समूह का Delaunay त्रिभुज ${\mathcal {P}}$ विमान में गेब्रियल ग्राफ, निकटतम पड़ोसी ग्राफ और न्यूनतम फैले पेड़ शामिल हैं ${\mathcal {P}}$.

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

नियमित त्रिभुज

बिंदुओं के एक समूह के कुछ त्रिभुज ${\mathcal {P}}\subset \mathbb {R} ^{d}$ के अंक उठाकर प्राप्त किया जा सकता है ${\mathcal {P}}$ में $\mathbb {R} ^{d+1}$ (जो एक समन्वय जोड़ने के लिए है $x_{d+1}$ के प्रत्येक बिंदु पर ${\mathcal {P}}$), बिंदुओं के उठाए गए सेट के उत्तल पतवार की गणना करके, और इस उत्तल पतवार के निचले चेहरों को वापस प्रक्षेपित करके $\mathbb {R} ^{d}$. इस तरह से बनाए गए त्रिभुजों को नियमित त्रिकोणासन के रूप में संदर्भित किया जाता है ${\mathcal {P}}$. जब बिन्दुओं को समीकरण के परवलयज पर ले जाया जाता है $x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}$, इस निर्माण का परिणाम Delaunay त्रिभुज है ${\mathcal {P}}$. ध्यान दें कि, इस निर्माण के लिए त्रिभुज प्रदान करने के लिए, बिंदुओं के उठाए गए सेट के निचले उत्तल पतवार को साधारण पॉलीटॉप होना चाहिए। Delaunay त्रिभुजों के मामले में, यह आवश्यक है कि नहीं $d+2$ के अंक ${\mathcal {P}}$ एक ही गोले में लेट जाओ।

प्लेन में कॉम्बिनेटरिक्स

किसी भी सेट का हर त्रिकोण ${\mathcal {P}}$ का $n$ विमान में अंक है $2n-h-2$ त्रिकोण और $3n-h-3$ किनारे कहाँ $h$ के अंकों की संख्या है ${\mathcal {P}}$ के उत्तल पतवार की सीमा में ${\mathcal {P}}$. यह सीधे यूलर विशेषता तर्क से आता है।

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

त्रिभुज बंटवारे एल्गोरिथम: बिंदु सेट के उत्तल पतवार का पता लगाएं ${\mathcal {P}}$ और इस पतवार को एक बहुभुज के रूप में त्रिकोणित करें। एक आंतरिक बिंदु चुनें और किनारों को उस त्रिकोण के तीन शीर्षों पर खींचें जिसमें यह शामिल है। इस प्रक्रिया को तब तक जारी रखें जब तक कि सभी आंतरिक बिंदु समाप्त न हो जाएं। इंक्रीमेंटल एल्गोरिद्म : के बिंदुओं को क्रमबद्ध करें ${\mathcal {P}}$ एक्स-निर्देशांक के अनुसार। पहले तीन बिंदु एक त्रिभुज का निर्धारण करते हैं। अगले बिंदु पर विचार करें $p$ आदेशित सेट में और इसे पहले से विचार किए गए सभी बिंदुओं से जोड़ दें $\{p_{1},...,p_{k}\}$ जो पी को दिख रहा है। के एक बिंदु को जोड़ने की इस प्रक्रिया को जारी रखें ${\mathcal {P}}$ एक समय में जब तक सभी ${\mathcal {P}}$ संसाधित किया गया।

विभिन्न एल्गोरिदम की समय जटिलता

निम्न तालिका विभिन्न इष्टतमता मानदंडों के तहत, विमान में बिंदु सेटों के त्रिभुजों के निर्माण के लिए समय जटिलता के परिणामों की रिपोर्ट करती है, जहां $n$ अंकों की संख्या है।

		minimize	maximize
minimum	angle		$O(n\log n)$ (Delaunay triangulation)
maximum		$O(n^{2}\log n)$
minimum	area	$O(n^{2})$	$O(n^{2}\log n)$
maximum		$O(n^{2}\log n)$
maximum	degree	NP-complete for degree of 7
maximum	eccentricity	$O(n^{3})$
minimum	edge length	$O(n\log n)$ (Closest pair of points problem)	NP-complete
maximum		$O(n^{2})$	$O(n\log n)$ (using the Convex hull)
sum of		NP-hard (Minimum-weight triangulation)
minimum	height		$O(n^{2}\log n)$
maximum	slope	$O(n^{3})$

यह भी देखें

• जाल पीढ़ी
• बहुभुज त्रिभुज

संदर्भ

• Bern, M.; Edelsbrunner, H.; Eppstein, D.; Mitchell, S.; Tan, T. S. (1993), "Edge insertion for optimal triangulations", Discrete and Computational Geometry, 10 (1): 47–65, doi:10.1007/BF02573962, MR 1215322
• Chazelle, Bernard; Guibas, Leo J.; Lee, D. T. (1985). "The power of geometric duality" (PDF). BIT. BIT Computer Science and Numerical Mathematics. 25 (1): 76–90. doi:10.1007/BF01934990. ISSN 0006-3835. S2CID 122411548.
• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry: Algorithms and Applications (3 ed.). Springer-Verlag.
• O'Rourke, Joseph; L. Devadoss, Satyan (2011). Discrete and Computational Geometry (1 ed.). Princeton University Press.
• Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1990). An O(n2log n) time algorithm for the MinMax angle triangulation. Proceedings of the sixth annual symposium on Computational geometry. SCG '90. ACM. pp. 44–52. CiteSeerX 10.1.1.66.2895. doi:10.1145/98524.98535. ISBN 0-89791-362-0.
• Edelsbrunner, Herbert; Tan, Tiow Seng (1991). A quadratic time algorithm for the minmax length triangulation. 32nd Annual Symposium on Foundations of Computer Science. pp. 414–423. CiteSeerX 10.1.1.66.8959. doi:10.1109/SFCS.1991.185400. ISBN 0-8186-2445-0.
• Fekete, Sándor P. (2012). "The Complexity of MaxMin Length Triangulation". arXiv:1208.0202v1 [cs.CG].
• Jansen, Klaus (1992). The Complexity of the Min-max Degree Triangulation Problem (PDF). 9th European Workshop on Computational Geometry. pp. 40–43.
• Lloyd, Errol Lynn (1977). On triangulations of a set of points in the plane. 18th Annual Symposium on Foundations of Computer Science. Switching and Automata Theory, 1974., IEEE Conference Record of 15Th Annual Symposium on. pp. 228–240. doi:10.1109/SFCS.1977.21. ISSN 0272-5428.
• Vassilev, Tzvetalin Simeonov (2005). Optimal Area Triangulation (PDF) (Ph.D.). University of Saskatchewan, Saskatoon. Archived from the original (PDF) on 2017-08-13. Retrieved 2013-06-15.