डेलाउने त्रिभुज

दिखाए गए परिधि के साथ विमान में डेलाउने त्रिभुज

गणित और कम्प्यूटेशनल ज्यामिति में एक सामान्य स्थिति में असतत बिन्दुओ के दिए गए समुच्चय $P$ के लिए डेलाउने त्रिभुज (जिसे डेलोन त्रिभुज के रूप में जाना जाता है) एक त्रिभुज $DT(P)$ है, जैसा कि $P$ में कोई भी बिंदु किसी त्रिभुज के परिवृत्त त्रिकोण के अंदर $DT(P)$ नही है। डेलाउने त्रिभुज में त्रिभुज के सभी कोणों के न्यूनतम कोण को अधिकतम करते हैं। वे स्लिवर त्रिकोण से बचते हैं। 1934 से इस विषय पर काम करने के लिए त्रिकोणीयकरण का नाम बोरिस डेलौने के नाम पर रखा गया है।^[1]

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

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

वोरोनोई आरेख के साथ संबंध

The Delaunay triangulation with all the circumcircles and their centers (in red).

Connecting the centers of the circumcircles produces the Voronoi diagram (in red).

सामान्य स्थिति में असतत बिंदु समुच्चय $P$ डेलाउने त्रिभुज $P$ के लिए वोरोनोई आरेख के दोहरे ग्राफ से मेल खाती है।

डेलाउने त्रिभुजों के परिबद्ध वृत्त वोरोनोई आरेख के शीर्ष हैं।

2डी स्थितियों में वोरोनोई शीर्ष किनारों के माध्यम से जुड़े हुए हैं। जो डेलाउने त्रिभुजों के आसन्न-संबंधों से प्राप्त किए जा सकते हैं। यदि दो त्रिकोण डेलाउने त्रिभुज में किनारे साझा करते हैं तो उनके परिकेन्द्रों को वोरोनोई टेसलेशन में किनारे से जोड़ा जाना है।

विशेष स्थितियों में जहां यह सम्बन्ध नहीं होता है। इसमें ऐसी स्थितियाँ सम्मिलित हैं:

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

डी-आयामी डेलाउने

( $d$ -आयामी) यूक्लिडियन स्पेस में बिन्दुओ के एक समुच्चय $P$ के लिए डेलाउने त्रिभुज एक त्रिभुज $DT(P)$ है। जैसा कि $P$ में कोई बिंदु $DT(P)$ में किसी $d$ सिम्प्लेक्स के परिधि हाइपरस्फीयर के अंदर नही है। यह ज्ञात है^[1] जिसके $P$ लिए एक अद्वितीय डेलाउने त्रिभुज आधुनिक है। यदि $P$ सामान्य स्थिति में बिंदुओं का एक समूह है। वह $P$ का एफ़िन हल है। $d$ -आयामी और $d + 2$ का कोई समुच्चय नहीं निर्देशित करता है। $P$ एक गेंद की सीमा पर स्थित है। जिसका आंतरिक भाग $P$ प्रतिच्छेद नहीं करता है।

बिंदुओं के एक समूह के डेलाउने त्रिभुज को खोजने की समस्या $d$ -आयामी यूक्लिडियन अंतरिक्ष को बिंदुओं के एक समुच्चय ( $d + 1$ )-विमीय स्थान के उत्तल हल को खोजने की समस्या में परिवर्तित किया जा सकता है। यह प्रत्येक बिंदु $p$ के बराबर एक अतिरिक्त समन्वय $| p | 2$ देकर किया जा सकता है। इस प्रकार इसे हाइपर-पैराबोलॉइड में बदलना (इसे लिफ्टिंग कहा जाता है) उत्तल हल के नीचे की ओर ले जाना (जैसा कि शीर्ष अंत-टोपी मूल से ऊपर की ओर है और इसे त्याग दिया जाना चाहिए) और मैपिंग पुनः $d$ -डायमेंशनल स्पेस अंतिम निर्देशांक को हटाकर किया जाना चाहिए। जैसा कि उत्तल हल प्रमुख हैं। इसलिए त्रिभुज है, यह मानते हुए कि उत्तल हल के सभी क्षेत्र सरल हैं। गैर-सरल पहलू केवल तब होते हैं जब मूल बिंदुओं के d + 2 एक ही d-हाइपरस्फीयर पर होते हैं। अर्थात् अंक सामान्य स्थिति में नहीं हैं।^[2]

गुण

उदाहरण कदम

एनीमेशन का प्रत्येक फ्रेम चार बिंदुओं का डेलाउने त्रिभुज दिखाता है। आधे पथ में त्रिकोणीय किनारा यह दर्शाता है कि डेलाउने त्रिभुज न्यूनतम कोण को अधिकतम करता है, न कि त्रिकोण के किनारे-लंबाई को अधिकतम करता है।

माना कि $n$ अंकों की संख्या हो और $d$ आयामों की संख्या हो।

त्रिभुज में सभी सरलताओं का मिलन बिंदुओं का उत्तल हल्स है।
डेलाउने त्रिभुज में $O\left(n^{\lceil d/2\rceil }\right)$ सरल सम्मिलित ।है^[3]
( $d = 2$ ) प्लेन में यदि वहाँ $b$ उत्तल हल्स पर उच्चतम है। जिससे बिंदुओं के किसी भी त्रिभुज में $2 n - 2 - b$ त्रिकोण अधिकतम होता है। इसके साथ ही एक बाहरी फेस स्थित होता है (यूलर विशेषता देखें)।
यदि प्वॉइसन प्रक्रिया के अनुसार समतल में निरंतर तीव्रता के साथ अंक वितरित किए जाते हैं। जिससे प्रत्येक शीर्ष पर औसतन छह प्रमुख त्रिकोण होते हैं। अधिक सामान्यतः एक ही प्रक्रिया के लिए $d$ आयाम केवल निकटतम $d$ कि औसत संख्या पर निर्भर करता है।^[4]
प्लेन में डेलाउने त्रिभुज न्यूनतम कोण को अधिकतम करता है। बिंदुओं के किसी भी अन्य त्रिभुज की तुलना में डेलाउने त्रिभुज में सबसे छोटा कोण कम से कम उतना ही बड़ा है, जितना किसी अन्य में सबसे छोटा कोण। चूंकि डेलाउने त्रिभुज आवश्यक रूप से अधिकतम कोण को कम नहीं करता है।^[5] डेलाउने त्रिभुज भी आवश्यक रूप से किनारों की लंबाई को कम नहीं करता है।
किसी भी डेलाउने त्रिभुज के परिगत एक वृत्त के आंतरिक भाग में कोई अन्य इनपुट बिंदु नहीं होता है।
यदि दो इनपुट बिंदुओं से होकर गुजरने वाले वृत्त के आंतरिक भाग में कोई अन्य इनपुट बिंदु नहीं है। जिससे दो बिंदुओं को जोड़ने वाला खंड दिए गए बिंदुओं के डेलाउने त्रिभुज का किनारा होता है।
बिंदुओं के एक समुच्चय के डेलाउने त्रिभुज के प्रत्येक त्रिभुज में $d$ -विमीय रिक्त स्थान बिंदुओं के प्रक्षेपण के उत्तल हल्स के एक क्षेत्र ( $d + 1$ )-विमीय परवलयज से मिलान करता है और इसके विपरीत भी कार्य को दर्शाता है।
निकटतम किसी भी बिंदु $p$ का $b$ पर $bp$ डेलाउने त्रिभुज में किनारे पर स्थित है क्योंकि निकटतम ग्राफ डेलाउने त्रिभुज का एक सब-ग्राफ को दर्शाता है।
डेलाउने त्रिभुज प्लेन ( $d = 2$ ) में एक ज्यामितीय स्पैनर है। डेलाउने किनारों के साथ-साथ दो शीर्षों के बीच का सबसे छोटा पथ उनके बीच यूक्लिडियन दूरी के 1.998 गुना से अधिक लंबा नहीं माना जाता है।^[6]

विज़ुअल डेलाउने परिभाषा: फ़्लिपिंग

उपरोक्त गुणों से एक महत्वपूर्ण विशेषता उत्पन्न होती है: दो त्रिभुजों $△ ABD, △ BCD$ को सामान्य किनारे $BD$ के साथ देखना (आंकड़े देखें)। यदि कोणों का योग $α + γ \leq 180°$ त्रिकोण डेलाउने नियम को पूरा करते हैं।

यह एक महत्वपूर्ण गुण है क्योंकि यह फ़्लिपिंग प्रणाली के उपयोग की अनुमति प्रदान करता है। यदि दो त्रिकोण डेलाउने की स्थिति को पूरा नहीं करते हैं। जिससे सामान्य किनारे $BD$ को बदलना सामान्य किनारे $AC$ के लिए दो त्रिभुज उत्पन्न करता है। जो डेलाउने नियम को पूर्णतयः सन्तुष्ट करते हैं:

Index.php?title=File:Delaunay geometry.png

यह त्रिभुज डेलाउने स्थिति (के योग) को पूरा नहीं करता है। ( $α$ और $γ$ 180° से बड़ा है)।
Index.php?title=File:Point inside circle - Delaunay condition broken.svg

त्रिभुजों का यह युग्म डेलाउने स्थिति को पूरा नहीं करता है (परिवृत्त के अन्दर के भाग में एक बिंदु है)।
Index.php?title=File:Edge Flip - Delaunay condition ok.svg

सामान्य किनारे को फ़्लिप करने से चार बिंदुओं के लिए एक वैध डेलाउने त्रिभुज का निर्माण होता है।

इस ऑपरेशन को फ्लिप कहा जाता है और इसे तीन और उच्च आयामों में सामान्यीकृत किया जा सकता है।^[7]

एल्गोरिदम

प्रयुक्त बिन्दु की जानकारी के लिए हमें एक शक्तिशाली और तेज़ उपाय करना चाहिए।

A, B, C

तीनों बिन्दु

D

के परिवृत्त में स्थित हैे।

डेलाउने त्रिकोण की गणना करने के लिए कई एल्गोरिदम यह पता लगाने के लिए तेजी से संचालन पर विश्वास करते हैं कि कब एक बिंदु त्रिकोण के परिवृत्त के अन्दर है और त्रिकोण और किनारों को संग्रहीत करने के लिए एक कुशल डेटा संरचना है। दो आयामों में बिंदु का पता लगाने का एक उपाय $D$ के परिवृत्त में स्थित है। जिससे $A, B, C$ निर्धारक का मूल्यांकन करना है:^[8]

{\begin{aligned}&{\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}\\[8pt]={}&{\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{2}\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}-D_{x})^{2}+(C_{y}-D_{y})^{2}\end{vmatrix}}>0\end{aligned}}

जब $A, B, C$ वामावर्त क्रम में क्रमबद्ध हैं। यह निर्धारक केवल तभी धनात्मक होता है। जब $D$ परिवृत्त के अंदर स्थित होता है।

फ्लिप एल्गोरिदम

जैसा कि ऊपरोक्त वर्णन किया गया है कि यदि एक त्रिभुज गैर-डेलाउने है। जिससे हम इसके किनारों में से एक को विपरीत रूप प्रदान कर सकते हैं। यह एक सीधे एल्गोरिथ्म की ओर जाता है। बिंदुओं के किसी भी त्रिभुज का निर्माण करें और तब तक किनारों को फ़्लिप करें। जब तक कि कोई त्रिभुज गैर-डेलाउने न हो। यह जानकारी प्राप्त हो सकती है कि $Ω(n 2)$ किनारा फ़्लिप करता है।^[9] चूंकि इस एल्गोरिथ्म को तीन और उच्च आयामों के लिए सामान्यीकृत किया जा सकता है। किन्तु इन स्थितियों में इसके अभिसरण का आश्वाशन नहीं प्राप्त होता है क्योंकि यह अंतर्निहित फ्लिप ग्राफ की कनेक्टिविटी के लिए वातानुकूलित है। यह ग्राफ बिंदुओं के द्वि-आयामी समुच्चय के लिए जुड़ा हुआ है। ^[7]

वृद्धिशील

डेलाउने त्रिभुज की कुशलतापूर्वक गणना करने का सबसे सीधा उपाय एक समय में बार-बार एक शीर्ष को जोड़ना है। ग्राफ़ के प्रभावित भागों को पुनः त्रिकोणित करना है। जब एक शीर्ष $v$ जोड़ा जाता है। हम तीन त्रिकोण में विभाजित होते हैं। जिसमें $v$ भी सम्मिलित होता है। फिर हम फ्लिप एल्गोरिथम संचालित करते हैं। सामान्य रूप से किया गया है। इसमें $O(n)$ समय लगेगा: हम सभी त्रिकोणों के माध्यम से खोजते हैं। जिसमें $v$ सम्मिलत है। फिर हम संभावित रूप से प्रत्येक त्रिकोण को उस स्थान से हटा देते हैं। फिर सम्पूर्ण रनटाइम $O(n 2)$ है।

यदि हम वर्टिकल को यादृच्छिक क्रम में सम्मिलित करते हैं। जिससे यह जानकारी प्राप्त होती है (कुछ जटिल प्रमाण द्वारा) कि प्रत्येक प्रविष्टि औसतन केवल $O(1)$ त्रिकोण फ़्लिप करेगी। चूंकि सामान्यतः यह कई और फ्लिप करेगा।^[10]

यह अभी भी बिंदु स्थान समय को सही करने के लिए छोड़ देता है। हम प्रदर्शन किए गए विभाजन और फ़्लिप के इतिहास को संग्रहीत कर सकते हैं। प्रत्येक त्रिभुज दो या तीन त्रिभुजों के लिए एक सूचक को संग्रहीत करता है। जो इसे प्रतिस्थापित करता है। उस त्रिकोण को खोजने के लिए जिसमें सम्मिलित $v$ है। हम मूल त्रिभुज से प्रारंभ करते हैं और उस सूचक का अनुसरण करते हैं। जो उस त्रिभुज की ओर निर्देश प्रदान करता है। जिसमें समाविष्ट $v$ उपस्थित होती है। जब तक हमें एक ऐसा त्रिभुज नहीं प्राप्त हो जाता है, जिसे समय के साथ बदला नहीं गया है। इसमें औसतन $O(log n)$ समय भी लगेगा। सभी शीर्षों पर यह $O(n log n)$ समय लेता है।^[11] जबकि प्रणाली उच्च आयाम तक फैली हुई है (जैसा कि एडेल्सब्रनर और शाह द्वारा सिद्ध किया गया है)।^[12] रनटाइम आयाम में यह घातीय हो सकता है। तथापि अंतिम डेलाउने त्रिभुज छोटा हो।

बाउयर-वाटसन एल्गोरिथ्म वृद्धिशील निर्माण के लिए एक और दृष्टिकोण प्रदान करता है। यह डेलाउने त्रिभुजों की गणना करने के लिए एज फ़्लिपिंग का एक विकल्प प्रदान करता है। जिसमें एक नया डाला गया शीर्ष उपस्थित होता है।

फ़्लिपिंग-आधारित एल्गोरिदम को समानांतर करना कठिन होता है क्योंकि कुछ निश्चित बिंदु (जैसे वैगन व्हील का केंद्र बिंदु) जोड़ने से $O(n)$ लगातार फ़्लिप ऊपर तक जा सकता है। ब्लेलोच एट अल^[13] रिप-एंड-टेंट के आधार पर वृद्धिशील एल्गोरिदम का एक और संस्करण प्रस्तावित किया। जो समानांतर एल्गोरिदम के पॉलीलॉगरिदमिक विश्लेषण के साथ व्यावहारिक और अत्यधिक समानांतर है।

फूट डालो और राज करो

दो आयामों में त्रिकोणासन के लिए विभाजन और जीत एल्गोरिथम प्राप्त की और स्कैचर द्वारा विकसित किया गया था और लियोनिदास जे. गुइबास और जॉर्ज स्टॉल्फी द्वारा सुधार किया गया था^[14]^[15] और बाद में ड्वायर द्वारा इसको सही किया।^[16] इस एल्गोरिथ्म में एक पुनरावर्ती रूप से दो समुच्चयों में कोने को विभाजित करने के लिए एक रेखा खींचता है। डेलाउने त्रिभुज की गणना प्रत्येक समुच्चय के लिए की जाती है और फिर दो समुच्चयों को विभाजन रेखा के साथ मिला दिया जाता है। कुछ अच्छी प्रणालीयों का प्रयोग करके मर्ज ऑपरेशन $O(n)$ समय के साथ ही किया जा सकता है। तो सम्पूर्ण चलने का समय $O(n log n)$ है।^[17]

कुछ विभिन्न प्रकार के बिंदु समुच्चयों के लिए, जैसे कि एक समान यादृच्छिक वितरण, विभाजन की रेखाओं को बुद्धिमानी से चुनकर अपेक्षित समय $O(n log n)$ को कम किया जा सकता है। जब तक कि सबसे खराब स्थिति के प्रदर्शन को बनाए रखते हुए इसका निर्णय किया जा सकता है।

एक त्रिभुज का प्रदर्शन करने के लिए एक फूट डालो और जीतो प्रतिमान $d$ आयाम डी-वाल में प्रस्तुत किया गया है। पी. सिग्नोनी, सी. मोंटानी, आर. स्कोपिग्नो द्वारा के द्वारा E^d" में डेलाउने त्रिभुज एल्गोरिथम एक तेज़ विभाजन और जीत प्राप्त करता है। ।^[18]

फूट डालो और राज्य करो एल्गोरिथ्म को क्रमिक रूप से सबसे तेज डीटी पीढ़ी प्रणाली के रूप में प्रदर्शित किया गया है।^[19]^[20]

स्वीपहुल

स्वीपहुल^[21] 2डी डेलाउने त्रिभुज के लिए एक हाइब्रिड तकनीक है जो एक रेडियल प्रोपेगेटिंग स्वीप-हल और एक फ़्लिपिंग एल्गोरिदम का उपयोग करती है। स्वीप-हल क्रमिक रूप से 2 डी बिंदुओं के रेडियल-सॉर्ट किए गए समुच्चय को पुनरावृत्त करके बनाया जाता है, और त्रिकोण को उत्तल हल्स के दृश्य भाग से जोड़ता है, जो एक गैर-अतिव्यापी त्रिभुज देता है। कोई इस तरह से एक उत्तल हल्स का निर्माण कर सकता है जब तक कि अंकों का क्रम इस बात की गारंटी देता है कि त्रिकोण के भीतर कोई बिंदु नहीं आएगा। किन्तु, रेडियल सॉर्टिंग को शुरू करने के लिए अत्यधिक डेलाउने होने से फ़्लिपिंग को कम करना चाहिए। इसके बाद इसे अंतिम पुनरावृत्त त्रिकोण फ़्लिपिंग चरण के साथ जोड़ा जाता है।

अनुप्रयोग

बिंदुओं के एक समूह का यूक्लिडियन न्यूनतम फैले हुए पेड़ समान बिंदुओं के डेलाउने त्रिभुज का एक उपसमुच्चय है^[22] और इसकी कुशलता से गणना करने के लिए इसका लाभ प्राप्त किया जा सकता है।

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

डेलौने टेसलेशन फील्ड एस्टिमेटर (डीटीएफई) के माध्यम से पॉइंट सैंपलिंग के घनत्व या तीव्रता को निर्धारित करने के लिए डेलाउने त्रिकोण का उपयोग किया जा सकता है।

एक विमान में 100 बिंदुओं के एक यादृच्छिक समुच्चय का डेलाउने त्रिभुज।

डेलाउने ट्राईएन्गुलेशन का उपयोग अधिकांशतः अंतरिक्ष-विच्छेदित सॉल्वरों जैसे कि परिमित तत्व विधि और भौतिकी सिमुलेशन की परिमित मात्रा विधि के लिए मेष पीढ़ी के लिए किया जाता है क्योंकि कोण की गारंटी और क्योंकि तेजी से त्रिभुज एल्गोरिदम विकसित किए गए हैं। विशिष्ट रूप से मेश किए जाने वाले डोमेन को मोटे साधारण कॉम्प्लेक्स के रूप में निर्दिष्ट किया जाता है। जाली को संख्यात्मक रूप से स्थिर होने के लिए इसे परिष्कृत किया जाना चाहिए। उदाहरण के लिए रूपर्ट के एल्गोरिथ्म का उपयोग करके।

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

विवश डेलाउने त्रिकोणासन ने स्वचालित ड्राइविंग और स्थलाकृतिक सर्वेक्षण में पथ नियोजन में अनुप्रयोगों को पाया है। ^[23]

यह भी देखें

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

संदर्भ

↑ ^1.0 ^1.1 Delaunay, Boris (1934). "Sur la sphère vide". Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles. 6: 793–800.
↑ Fukuda, Komei. "बहुफलकीय संगणना में अक्सर पूछे जाने वाले प्रश्न". www.cs.mcgill.ca. Retrieved 29 October 2018.
↑ Seidel, Raimund (1995). "The upper bound theorem for polytopes: an easy proof of its asymptotic version". Computational Geometry. 5 (2): 115–116. doi:10.1016/0925-7721(95)00013-Y.
↑ Meijering, J. L. (1953), "Interface area, edge length, and number of vertices in crystal aggregates with random nucleation" (PDF), Philips Research Reports, 8: 270–290, archived from the original (PDF) on 2017-03-08. As cited by Dwyer, Rex A. (1991), "Higher-dimensional Voronoĭ diagrams in linear expected time", Discrete and Computational Geometry, 6 (4): 343–367, doi:10.1007/BF02574694, MR 1098813.
↑ Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1992), "An O(n² log n) time algorithm for the minmax angle triangulation" (PDF), SIAM Journal on Scientific and Statistical Computing, 13 (4): 994–1008, CiteSeerX 10.1.1.66.2895, doi:10.1137/0913058, MR 1166172, archived from the original (PDF) on 2017-02-09, retrieved 2017-10-24.
↑ Xia, Ge (2013), "The stretch factor of the Delaunay triangulation is less than 1.998", SIAM Journal on Computing, 42 (4): 1620–1659, arXiv:1103.4361, doi:10.1137/110832458, MR 3082502, S2CID 6646528
↑ ^7.0 ^7.1 De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Vol. 25. Springer.
↑ Guibas, Leonidas; Stolfi, Jorge (1985). "Primitives for the manipulation of general subdivisions and the computation of Voronoi". ACM Transactions on Graphics. 4 (2): 74–123. doi:10.1145/282918.282923. S2CID 52852815.
↑ Hurtado, F.; Noy, M.; Urrutia, J. (1999). "Flipping Edges in Triangulations". Discrete & Computational Geometry. 22 (3): 333–346. doi:10.1007/PL00009464.
↑ Guibas, Leonidas J.; Knuth, Donald E.; Sharir, Micha (1992). "Randomized incremental construction of Delaunay and Voronoi diagrams". Algorithmica. 7 (1–6): 381–413. doi:10.1007/BF01758770. S2CID 3770886.
↑ de Berg, Mark; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Computational Geometry: Algorithms and Applications (PDF). Springer-Verlag. ISBN 978-3-540-77973-5. Archived from the original (PDF) on 2009-10-28. Retrieved 2010-02-23.
↑ Edelsbrunner, Herbert; Shah, Nimish (1996). "Incremental Topological Flipping Works for Regular Triangulations". Algorithmica. 15 (3): 223–241. doi:10.1007/BF01975867. S2CID 12976796.
↑ Blelloch, Guy; Gu, Yan; Shun, Julian; and Sun, Yihan. Parallelism in Randomized Incremental Algorithms Archived 2018-04-25 at the Wayback Machine. SPAA 2016. doi:10.1145/2935764.2935766.
↑ Guibas, Leonidas; Stolfi, Jorge (April 1985). "सामान्य उपविभागों में हेराफेरी के लिए आदिम और वोरोनोई की गणना". ACM Transactions on Graphics. 4 (2): 74–123. doi:10.1145/282918.282923. S2CID 52852815.
↑ "विमान में विवश delaunay त्रिभुजों की गणना". www.geom.uiuc.edu. Archived from the original on 22 September 2017. Retrieved 25 April 2018.
↑ Dwyer, Rex A. (November 1987). "Delaunay Triangulations के निर्माण के लिए एक तेज़ फूट डालो और जीतो एल्गोरिथम". Algorithmica. 2 (1–4): 137–151. doi:10.1007/BF01840356. S2CID 10828441.
↑ Leach, G. (June 1992). "वर्स्ट-केस ऑप्टिमल डेलाउने ट्रायंगुलेशन एल्गोरिदम में सुधार". 4th Canadian Conference on Computational Geometry. CiteSeerX 10.1.1.56.2323.
↑ Cignoni, P.; C. Montani; R. Scopigno (1998). "DeWall: A fast divide and conquer Delaunay triangulation algorithm in E^d". Computer-Aided Design. 30 (5): 333–341. doi:10.1016/S0010-4485(97)00082-1.
↑ A Comparison of Sequential Delaunay Triangulation Algorithms "Archived copy" (PDF). Archived from the original (PDF) on 2012-03-08. Retrieved 2010-08-18.{{cite web}}: CS1 maint: archived copy as title (link)
↑ "त्रिभुज एल्गोरिदम और डेटा संरचनाएं". www.cs.cmu.edu. Archived from the original on 10 October 2017. Retrieved 25 April 2018.
↑ "एस हल" (PDF). s-hull.org. Archived (PDF) from the original on 2013-10-27. Retrieved 25 April 2018.
↑ Franz Aurenhammer; Rolf Klein; Der-tsai Lee (26 June 2013). वोरोनोई आरेख और डेलाउने त्रिभुज. World Scientific Publishing Company. pp. 197–. ISBN 978-981-4447-65-2.
↑ Sterling J Anderson; Sisir B. Karumanchi; Karl Iagnemma (5 July 2012). "Constraint-based planning and control for safe, semi-autonomous operation of vehicles" (PDF). 2012 IEEE Intelligent Vehicles Symposium. IEEE. doi:10.1109/IVS.2012.6232153. Archived from the original (PDF) on 28 February 2019. Retrieved 27 February 2019.

बाहरी संबंध

"डेलाउने triangulation". Wolfram MathWorld. Retrieved April 2010.

सॉफ्टवेयर

CGAL, कम्प्यूटेशनल ज्योमेट्री एल्गोरिथम लाइब्रेरी में डेलाउने त्रिभुज:
- मैरियट यविनेक। 2D त्रिभुज। अप्रैल 2010 को पुनःप्राप्त।
- पिओन, सिल्वेन; मोनिक टीलौड|टीलौड, मोनिक। 3D त्रिभुज। अप्रैल 2010 को पुनःप्राप्त।
- हॉर्नस, शमूएल; डिविलर्स, ओलिवियर; जैमिन, क्लेमेंट। dD Triangulations।
- हर्ट, सुसान; सील, माइकल। dD कॉन्वेक्स हल्स और डेलाउने ट्रायंगुलेशन। अप्रैल 2010 को पुनःप्राप्त।
Poly2Tri: इंक्रीमेंटल विवश डेलाउने त्रिकोण। ओपन सोर्स सी ++ कार्यान्वयन। अप्रैल 2019 को पुनःप्राप्त।
डेलाउने त्रिकोणीय निर्माण को विभाजित करें और जीतें। ओपन सोर्स C99 कार्यान्वयन। अप्रैल 2019 को पुनःप्राप्त।
CDT: C++ में विवश डेलाउने Triangulation। ओपन सोर्स सी ++ कार्यान्वयन। अगस्त 2022 को पुनःप्राप्त।

श्रेणी:त्रिकोण (ज्यामिति) श्रेणी:ज्यामितीय एल्गोरिदम

[Delaunay1934-1] 1.0 ^1.1 Delaunay, Boris (1934). "Sur la sphère vide". Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles. 6: 793–800.

[2] Fukuda, Komei. "बहुफलकीय संगणना में अक्सर पूछे जाने वाले प्रश्न". www.cs.mcgill.ca. Retrieved 29 October 2018.

[3] Seidel, Raimund (1995). "The upper bound theorem for polytopes: an easy proof of its asymptotic version". Computational Geometry. 5 (2): 115–116. doi:10.1016/0925-7721(95)00013-Y.

[4] Meijering, J. L. (1953), "Interface area, edge length, and number of vertices in crystal aggregates with random nucleation" (PDF), Philips Research Reports, 8: 270–290, archived from the original (PDF) on 2017-03-08. As cited by Dwyer, Rex A. (1991), "Higher-dimensional Voronoĭ diagrams in linear expected time", Discrete and Computational Geometry, 6 (4): 343–367, doi:10.1007/BF02574694, MR 1098813.

[5] Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1992), "An O(n² log n) time algorithm for the minmax angle triangulation" (PDF), SIAM Journal on Scientific and Statistical Computing, 13 (4): 994–1008, CiteSeerX 10.1.1.66.2895, doi:10.1137/0913058, MR 1166172, archived from the original (PDF) on 2017-02-09, retrieved 2017-10-24.

[6] Xia, Ge (2013), "The stretch factor of the Delaunay triangulation is less than 1.998", SIAM Journal on Computing, 42 (4): 1620–1659, arXiv:1103.4361, doi:10.1137/110832458, MR 3082502, S2CID 6646528

[DRS-7] 7.0 ^7.1 De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Vol. 25. Springer.

[8] Guibas, Leonidas; Stolfi, Jorge (1985). "Primitives for the manipulation of general subdivisions and the computation of Voronoi". ACM Transactions on Graphics. 4 (2): 74–123. doi:10.1145/282918.282923. S2CID 52852815.

[hurtado-9] Hurtado, F.; Noy, M.; Urrutia, J. (1999). "Flipping Edges in Triangulations". Discrete & Computational Geometry. 22 (3): 333–346. doi:10.1007/PL00009464.

[10] Guibas, Leonidas J.; Knuth, Donald E.; Sharir, Micha (1992). "Randomized incremental construction of Delaunay and Voronoi diagrams". Algorithmica. 7 (1–6): 381–413. doi:10.1007/BF01758770. S2CID 3770886.

[deBerg-11] Berg, Mark; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Computational Geometry: Algorithms and Applications (PDF). Springer-Verlag. ISBN 978-3-540-77973-5. Archived from the original (PDF) on 2009-10-28. Retrieved 2010-02-23.

[12] Edelsbrunner, Herbert; Shah, Nimish (1996). "Incremental Topological Flipping Works for Regular Triangulations". Algorithmica. 15 (3): 223–241. doi:10.1007/BF01975867. S2CID 12976796.

[Parallel-13] Blelloch, Guy; Gu, Yan; Shun, Julian; and Sun, Yihan. Parallelism in Randomized Incremental Algorithms Archived 2018-04-25 at the Wayback Machine. SPAA 2016. doi:10.1145/2935764.2935766.

[14] Guibas, Leonidas; Stolfi, Jorge (April 1985). "सामान्य उपविभागों में हेराफेरी के लिए आदिम और वोरोनोई की गणना". ACM Transactions on Graphics. 4 (2): 74–123. doi:10.1145/282918.282923. S2CID 52852815.

[15] "विमान में विवश delaunay त्रिभुजों की गणना". www.geom.uiuc.edu. Archived from the original on 22 September 2017. Retrieved 25 April 2018.

[16] Dwyer, Rex A. (November 1987). "Delaunay Triangulations के निर्माण के लिए एक तेज़ फूट डालो और जीतो एल्गोरिथम". Algorithmica. 2 (1–4): 137–151. doi:10.1007/BF01840356. S2CID 10828441.

[Leach1992-17] Leach, G. (June 1992). "वर्स्ट-केस ऑप्टिमल डेलाउने ट्रायंगुलेशन एल्गोरिदम में सुधार". 4th Canadian Conference on Computational Geometry. CiteSeerX 10.1.1.56.2323.

[18] Cignoni, P.; C. Montani; R. Scopigno (1998). "DeWall: A fast divide and conquer Delaunay triangulation algorithm in E^d". Computer-Aided Design. 30 (5): 333–341. doi:10.1016/S0010-4485(97)00082-1.

[19] A Comparison of Sequential Delaunay Triangulation Algorithms "Archived copy" (PDF). Archived from the original (PDF) on 2012-03-08. Retrieved 2010-08-18.{{cite web}}: CS1 maint: archived copy as title (link)

[20] "त्रिभुज एल्गोरिदम और डेटा संरचनाएं". www.cs.cmu.edu. Archived from the original on 10 October 2017. Retrieved 25 April 2018.

[21] "एस हल" (PDF). s-hull.org. Archived (PDF) from the original on 2013-10-27. Retrieved 25 April 2018.

[AurenhammerKlein2013-22] Franz Aurenhammer; Rolf Klein; Der-tsai Lee (26 June 2013). वोरोनोई आरेख और डेलाउने त्रिभुज. World Scientific Publishing Company. pp. 197–. ISBN 978-981-4447-65-2.

[23] Sterling J Anderson; Sisir B. Karumanchi; Karl Iagnemma (5 July 2012). "Constraint-based planning and control for safe, semi-autonomous operation of vehicles" (PDF). 2012 IEEE Intelligent Vehicles Symposium. IEEE. doi:10.1109/IVS.2012.6232153. Archived from the original (PDF) on 28 February 2019. Retrieved 27 February 2019.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

Anonymous

Search

डेलाउने त्रिभुज

Namespaces

More

Page actions

Contents

वोरोनोई आरेख के साथ संबंध

डी-आयामी डेलाउने

गुण

विज़ुअल डेलाउने परिभाषा: फ़्लिपिंग

एल्गोरिदम

फ्लिप एल्गोरिदम

वृद्धिशील

फूट डालो और राज करो

स्वीपहुल

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

सॉफ्टवेयर

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डेलाउने त्रिभुज

वोरोनोई आरेख के साथ संबंध

डी-आयामी डेलाउने

गुण

विज़ुअल डेलाउने परिभाषा: फ़्लिपिंग

एल्गोरिदम

फ्लिप एल्गोरिदम

वृद्धिशील

फूट डालो और राज करो

स्वीपहुल

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

सॉफ्टवेयर

Navigation

Wiki tools

Page tools

Other projects

Hidden categories