वोरोनोई आरेख

File:Euclidean Voronoi diagram.svg

20 अंक और उनके वोरोनोई सेल (बड़ा संस्करण #चित्रण)

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

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

सबसे सरल मामला

सबसे सरल मामले में, पहली तस्वीर में दिखाया गया है, हमें बिंदुओं का एक सीमित समुच्चय दिया गया है {p₁, ..., पी_n} यूक्लिडियन विमान में। इस मामले में प्रत्येक साइट पी_k बस एक बिंदु है, और इसकी संबंधित वोरोनोई सेल आर_k यूक्लिडियन तल में प्रत्येक बिंदु से मिलकर बनता है जिसकी दूरी p से है_k किसी अन्य पी से इसकी दूरी से कम या उसके बराबर है_k. ऐसा प्रत्येक सेल हाफ-स्पेस (ज्योमेट्री)|हाफ-स्पेस के इंटरसेक्शन से प्राप्त किया जाता है, और इसलिए यह एक उत्तल पॉलीटॉप|(उत्तल) पॉलीहेड्रॉन है। वोरोनोई आरेख के रेखा खंड विमान के सभी बिंदु हैं जो दो निकटतम साइटों के समान हैं। वोरोनोई कोने (नोड (ग्राफ़ सिद्धांत) एस) तीन (या अधिक) साइटों के समतुल्य बिंदु हैं।

औपचारिक परिभाषा

होने देना ${\textstyle X}$ दूरी समारोह के साथ एक मीट्रिक स्थान बनें ${\textstyle d}$. होने देना ${\textstyle K}$ सूचकांकों का एक समुच्चय बनें और दें ${\textstyle (P_{k})_{k\in K}}$ अंतरिक्ष में गैर-खाली उपसमुच्चय (साइटों) का एक टपल (आदेशित संग्रह) बनें ${\textstyle X}$. वोरोनोई सेल, या वोरोनोई क्षेत्र, ${\textstyle R_{k}}$, साइट से जुड़ा हुआ है ${\textstyle P_{k}}$ में सभी बिंदुओं का समुच्चय है ${\textstyle X}$ किससे दूरी ${\textstyle P_{k}}$ अन्य स्थलों से उनकी दूरी से अधिक नहीं है ${\textstyle P_{j}}$, कहाँ पे ${\textstyle j}$ क्या कोई इंडेक्स इससे अलग है ${\textstyle k}$. दूसरे शब्दों में, अगर ${\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}$ बिंदु के बीच की दूरी को दर्शाता है ${\textstyle x}$ और उपसमुच्चय ${\textstyle A}$, फिर

$$R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{for all}}\;j\neq k\}$$

वोरोनोई आरेख केवल कोशिकाओं का टपल है ${\textstyle (R_{k})_{k\in K}}$. सिद्धांत रूप में, कुछ साइटें एक दूसरे को काट सकती हैं और यहां तक ​​​​कि मेल भी खा सकती हैं (दुकानों का प्रतिनिधित्व करने वाली साइटों के लिए एक आवेदन नीचे वर्णित है), लेकिन आमतौर पर उन्हें अलग माना जाता है। इसके अलावा, परिभाषा में असीम रूप से कई साइटों की अनुमति है (इस समुच्चयिंग में संख्याओं और क्रिस्टलोग्राफी की ज्यामिति में अनुप्रयोग हैं), लेकिन फिर से, कई मामलों में केवल बहुत सी साइटों पर विचार किया जाता है।

विशेष मामले में जहां अंतरिक्ष एक परिमित-आयामी यूक्लिडियन अंतरिक्ष है, प्रत्येक साइट एक बिंदु है, वहाँ बहुत सारे बिंदु हैं और वे सभी अलग-अलग हैं, फिर वोरोनोई कोशिकाएं उत्तल पॉलीटॉप हैं और उन्हें संयोजन के तरीके से प्रदर्शित किया जा सकता है उनके कोने, भुजाएँ, द्वि-आयामी चेहरे आदि। कभी-कभी प्रेरित संयोजन संरचना को वोरोनोई आरेख के रूप में संदर्भित किया जाता है। सामान्य तौर पर, वोरोनोई कोशिकाएं उत्तल या जुड़ी भी नहीं हो सकती हैं।

सामान्य यूक्लिडियन स्थान में, हम औपचारिक परिभाषा को सामान्य शब्दों में फिर से लिख सकते हैं। प्रत्येक वोरोनोई बहुभुज ${\textstyle R_{k}}$ एक जनरेटर बिंदु से जुड़ा हुआ है ${\textstyle P_{k}}$. होने देना ${\textstyle X}$ यूक्लिडियन अंतरिक्ष में सभी बिंदुओं का समुच्चय हो। होने देना ${\textstyle P_{1}}$ एक बिंदु बनें जो अपना वोरोनोई क्षेत्र उत्पन्न करता है ${\textstyle R_{1}}$, ${\textstyle P_{2}}$ जो उत्पन्न करता है ${\textstyle R_{2}}$, तथा ${\textstyle P_{3}}$ जो उत्पन्न करता है ${\textstyle R_{3}}$, और इसी तरह। फिर, जैसा कि ट्रान एट अल द्वारा व्यक्त किया गया है, यूक्लिडियन विमान में वोरोनोई आरेख में किसी भी अन्य जनरेटर बिंदु की तुलना में वोरोनोई बहुभुज के सभी स्थान उस बहुभुज के जनरेटर बिंदु के करीब हैं।

चित्रण

एक साधारण उदाहरण के रूप में, एक शहर में दुकानों के समूह पर विचार करें। मान लीजिए हम किसी दुकान के ग्राहकों की संख्या का अनुमान लगाना चाहते हैं। अन्य सभी समान (कीमत, उत्पाद, सेवा की गुणवत्ता, आदि) होने के साथ, यह मान लेना उचित है कि ग्राहक अपनी पसंदीदा दुकान को केवल दूरी के आधार पर चुनते हैं: वे अपने निकटतम स्थित दुकान पर जाएंगे। इस मामले में वोरोनोई सेल $R_{k}$ किसी दिए गए दुकान का $P_{k}$ इस दुकान पर जाने वाले संभावित ग्राहकों की संख्या पर एक मोटा अनुमान देने के लिए इस्तेमाल किया जा सकता है (जो हमारे शहर में एक बिंदु द्वारा तैयार किया गया है)।

अधिकांश शहरों के लिए, परिचित का उपयोग करके बिंदुओं के बीच की दूरी को मापा जा सकता है यूक्लिडियन दूरी:

$\ell _{2}=d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]={\sqrt {\left(a_{1}-b_{1}\right)^{2}+\left(a_{2}-b_{2}\right)^{2}}}$

या मैनहट्टन दूरी:

$d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]=\left|a_{1}-b_{1}\right|+\left|a_{2}-b_{2}\right|$.

अलग-अलग दूरी के मेट्रिक्स के लिए संबंधित वोरोनोई आरेख अलग-अलग दिखते हैं।

Voronoi diagrams of 20 points under two different metrics

File:Euclidean Voronoi diagram.svg

Euclidean distance

Manhattan distance

गुण

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

इतिहास और अनुसंधान

वोरोनोई आरेखों के अनौपचारिक उपयोग को 1644 में डेसकार्टेस में खोजा जा सकता है। पीटर गुस्ताव लेज्यून डिरिचलेट ने 1850 में द्विघात रूपों के अपने अध्ययन में द्वि-आयामी और तीन-आयामी वोरोनोई आरेखों का उपयोग किया। ब्रिटिश चिकित्सक जॉन स्नो (चिकित्सक) ने 1854 में एक वोरोनोई-जैसे आरेख का उपयोग यह बताने के लिए किया कि कैसे 1854 ब्रॉड स्ट्रीट हैजा के प्रकोप में मरने वाले अधिकांश लोग संक्रमित सोहो#ब्रॉड स्ट्रीट पंप के करीब किसी अन्य पानी के पंप की तुलना में रहते थे।

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

उदाहरण

Error creating thumbnail:

यह एक 3डी बॉक्स में बिंदुओं के एक यादृच्छिक समुच्चय के वोरोनोई आरेख का एक टुकड़ा है। सामान्य तौर पर, 3डी वोरोनोई टेसलेशन का एक क्रॉस सेक्शन स्वयं 2डी वोरोनोई टेसलेशन नहीं है। (कोशिकाएँ सभी उत्तल समुच्चय बहुतल हैं।)

दो या तीन आयामों में बिंदुओं के नियमित जाली (समूह) के वोरोनोई टेसेलेशन कई परिचित टेसेलेशन को जन्म देते हैं।

• एक 2डी जाली बिंदु समरूपता के साथ समान हेक्सागोन्स के साथ एक अनियमित छत्ते का टेसलेशन देती है; नियमित त्रिकोणीय जाली के मामले में यह नियमित है; एक आयताकार जाली के मामले में हेक्सागोन पंक्तियों और स्तंभों में आयतों में कम हो जाते हैं; एक स्क्वायर (ज्यामिति) जाली वर्गों का नियमित रूप से टेसलेशन देती है; ध्यान दें कि आयत और वर्ग अन्य जाली द्वारा भी उत्पन्न किए जा सकते हैं (उदाहरण के लिए वैक्टर (1,0) और (1/2,1/2) द्वारा परिभाषित जाली वर्ग देता है)।
• एक साधारण घन जाली घन मधुकोश देती है।
• एक हेक्सागोनल क्लोज-पैक जाली ट्रैपेज़-रोम्बिक डोडेकाहेड्रॉन के साथ अंतरिक्ष का एक टेसलेशन देती है|ट्रेपेज़-रोम्बिक डोडेकाहेड्रा।
• एक फलक-केन्द्रित घनीय जालक समचतुर्भुज द्वादशफलक के साथ अंतरिक्ष का एक पुंज बनाता है।
• एक शरीर-केंद्रित क्यूबिक जाली काटे गए ऑक्टाहेड्रॉन के साथ अंतरिक्ष का एक टेसलेशन देता है।
• एक दूसरे के केंद्रों के साथ संरेखित नियमित त्रिकोणीय जाली वाले समानांतर विमान हेक्सागोनल प्रिज्मीय मधुकोश देते हैं।
• कुछ शरीर-केन्द्रित चतुष्कोणीय जालक रोम्बो-हेक्सागोनल डोडेकाहेड्रॉन|रहोमो-हेक्सागोनल डोडेकाहेड्रा के साथ अंतरिक्ष का एक पुंज बनाते हैं।

असतत समुच्चय X में x के साथ बिंदुओं (x, y) के समुच्चय के लिए और असतत समुच्चय Y में y के लिए, हमें आयताकार टाइलें मिलती हैं जिनके केंद्र आवश्यक नहीं हैं।

उच्च-क्रम वोरोनोई आरेख

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

उच्च-क्रम वाले वोरोनोई आरेखों को पुनरावर्ती रूप से उत्पन्न किया जा सकता है। एन उत्पन्न करने के लिए^वां-समुच्चय S से वोरोनोई डायग्राम ऑर्डर करें, (n − 1) से शुरू करें^वां-आदेश आरेख और X={x₁, एक्स₂, ..., एक्स_n−1} समुच्चय S − X पर उत्पन्न वोरोनोई आरेख के साथ।

सबसे दूर-बिंदु वोरोनोई आरेख

n बिंदुओं के एक समुच्चय के लिए (n − 1)^{वें-क्रम वोरोनोई आरेख को सबसे दूर-बिंदु वोरोनोई आरेख कहा जाता है।}

बिंदुओं के दिए गए समुच्चय के लिए S = {p₁, पी₂, ..., पी_n} सबसे दूर का बिंदु वोरोनोई आरेख विमान को कोशिकाओं में विभाजित करता है जिसमें P का वही बिंदु सबसे दूर का बिंदु है। पी के एक बिंदु में सबसे दूर-बिंदु वोरोनोई आरेख में एक सेल है अगर और केवल अगर यह पी के उत्तल पतवार का शीर्ष है। एच = {एच₁, एच₂, ..., एच_k} P का उत्तल पतवार हो; फिर सबसे दूर का बिंदु वोरोनोई आरेख विमान के k कोशिकाओं में एक उपखंड है, H में प्रत्येक बिंदु के लिए एक, इस संपत्ति के साथ कि एक बिंदु q एक साइट h के अनुरूप सेल में स्थित है।_i अगर और केवल अगर डी (क्यू, एच_i)> डी (क्यू, पी_j) प्रत्येक पी के लिए_j∈ एस एच के साथ_i ≠ पी_j, जहां d(p, q) दो बिंदुओं p और q के बीच यूक्लिडियन दूरी है। सबसे दूर-बिंदु वोरोनोई आरेख में कोशिकाओं की सीमाओं में एक वास्तविक वृक्ष की संरचना होती है, जिसके पत्तों के रूप में अनंत रे (गणित) होते हैं। हर परिमित पेड़ एक दूर-बिंदु वोरोनोई आरेख से इस तरह से बने पेड़ के लिए आइसोमोर्फिक है।

सामान्यीकरण और विविधताएं

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

बिंदुओं के एक समूह का अनुमानित वोरोनोई आरेख। वोरोनोई कोशिकाओं की फ़ज़ी सीमा में मिश्रित रंगों पर ध्यान दें।

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

का वोरोनोई आरेख $n$ में इंगित करता है $d$-आयामी स्थान हो सकता है ${\textstyle O(n^{\lceil d/2\rceil })}$ कोने, इसके स्पष्ट विवरण को संग्रहीत करने के लिए आवश्यक मेमोरी की मात्रा के लिए समान सीमा की आवश्यकता होती है। इसलिए, वोरोनोई आरेख अक्सर मध्यम या उच्च आयामों के लिए संभव नहीं होते हैं। अनुमानित वोरोनोई आरेखों का उपयोग करने के लिए एक अधिक स्थान-कुशल विकल्प है। वोरोनोई आरेख अन्य ज्यामितीय संरचनाओं से भी संबंधित हैं जैसे कि औसत दर्जे का अक्ष (जिसने छवि विभाजन, ऑप्टिकल वर्ण पहचान और अन्य कम्प्यूटेशनल अनुप्रयोगों में आवेदन पाया है), सीधे कंकाल और ज़ोन आरेख।

अनुप्रयोग

मौसम विज्ञान / जल विज्ञान

इसका उपयोग मौसम विज्ञान और इंजीनियरिंग जल विज्ञान में एक क्षेत्र (वाटरशेड) पर स्टेशनों के अवक्षेपण डेटा के भार का पता लगाने के लिए किया जाता है। बहुभुज उत्पन्न करने वाले बिंदु वे विभिन्न स्टेशन हैं जो वर्षा डेटा रिकॉर्ड करते हैं। लम्ब समद्विभाजक किन्हीं दो स्टेशनों को मिलाने वाली रेखा पर खींचे जाते हैं। इसके परिणामस्वरूप स्टेशनों के चारों ओर बहुभुज बन जाते हैं। क्षेत्र $(A_{i})$ स्पर्श करने वाले स्टेशन बिंदु को स्टेशन के प्रभाव क्षेत्र के रूप में जाना जाता है। औसत वर्षा की गणना सूत्र द्वारा की जाती है ${\bar {P}}={\frac {\sum A_{i}P_{i}}{\sum A_{i}}}$

See also: Delaunay triangulation § Applications

मानविकी

• शास्त्रीय पुरातत्व में, विशेष रूप से कला के इतिहास में, मूर्ति के सिरों की समरूपता का विश्लेषण किया जाता है ताकि यह निर्धारित किया जा सके कि किस प्रकार की मूर्ति एक अलग सिर से संबंधित हो सकती है। इसका एक उदाहरण जिसने वोरोनोई कोशिकाओं का उपयोग किया, वह सबौरॉफ सिर की पहचान थी, जिसने एक उच्च-रिज़ॉल्यूशन बहुभुज जाल का उपयोग किया।* डायलेक्टोमेट्री में, सर्वेक्षण बिंदुओं के बीच कथित भाषाई निरंतरता को इंगित करने के लिए वोरोनोई कोशिकाओं का उपयोग किया जाता है।

प्राकृतिक विज्ञान

File:Voronoi growth euclidean.gif

बीज से बाहर की ओर रेडियल वृद्धि से एक वोरोनोई टेसलेशन निकलता है।

* जीव विज्ञान में, वोरोनोई आरेखों का उपयोग सेल (जीव विज्ञान) सहित कई विभिन्न जैविक संरचनाओं के मॉडल के लिए किया जाता है। और कैंसेलस बोन | बोन माइक्रोआर्किटेक्चर। दरअसल, वोरोनोई टेसेलेशन जैविक ऊतकों के संगठन को संचालित करने वाले भौतिक अवरोधों को समझने के लिए एक ज्यामितीय उपकरण के रूप में काम करते हैं। <रेफरी नाम = सांचेज़-गुटिएरेज़ 77-88>Sanchez-Gutierrez, D.; Tozluoglu, M.; Barry, J. D.; Pascual, A.; Mao, Y.; Escudero, L. M. (2016-01-04). "मौलिक भौतिक कोशिकीय बाधाएँ ऊतकों के स्व-संगठन को चलाती हैं". The EMBO Journal. 35 (1): 77–88. doi:10.15252/embj.201592374. PMC 4718000. PMID 26598531.</रेफरी>

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

रेफरी>Feinstein, Joseph; Shi, Wentao; Ramanujam, J.; Brylinski, Michal (2021). Ballante, Flavio (ed.). बायोनोई: मशीन लर्निंग अनुप्रयोगों के लिए प्रोटीन में लिगेंड-बाध्यकारी साइटों का एक वोरोनोई आरेख-आधारित प्रतिनिधित्व. pp. 299–312. doi:10.1007/978-1-0716-1209-5_17. ISBN 978-1-0716-1209-5. PMID 33759134. S2CID 232338911. Retrieved 2021-04-23. {{cite book}}: |work= ignored (help)</ रेफ> अन्य अनुप्रयोगों में, अणु में नाभिक की स्थिति द्वारा परिभाषित वोरोनोई कोशिकाओं का उपयोग आंशिक आवेशों की गणना के लिए किया जाता है। यह वोरोनोई विरूपण घनत्व विधि का उपयोग करके किया जाता है।

• खगोलभौतिकी में, वोरोनोई आरेखों का उपयोग छवियों पर अनुकूली चौरसाई क्षेत्रों को उत्पन्न करने के लिए किया जाता है, प्रत्येक पर सिग्नल फ्लक्स जोड़ते हैं। इन प्रक्रियाओं का मुख्य उद्देश्य सभी छवियों पर अपेक्षाकृत स्थिर सिग्नल-टू-शोर अनुपात बनाए रखना है।
• कम्प्यूटेशनल द्रव गतिकी में, बिंदुओं के एक समुच्चय के वोरोनोई टेसलेशन का उपयोग परिमित मात्रा विधियों में उपयोग किए जाने वाले कम्प्यूटेशनल डोमेन को परिभाषित करने के लिए किया जा सकता है, उदा। जैसा कि मूविंग-मेश कॉस्मोलॉजी कोड AREPO में है। रेफरी>Springel, Volker (2010). "E pur si muove: गैलिलियन-इनवेरिएंट कॉस्मोलॉजिकल हाइड्रोडायनामिकल सिमुलेशन ऑन ए मूविंग मेश". MNRAS. 401 (2): 791–851. arXiv:0901.4107. Bibcode:2010MNRAS.401..791S. doi:10.1111/j.1365-2966.2009.15715.x. S2CID 119241866.</रेफरी>
• कम्प्यूटेशनल भौतिकी में, उच्च ऊर्जा घनत्व भौतिकी में एक्स-रे फ़ोटो और प्रोटॉन रेडियोग्राफी के साथ किसी वस्तु के प्रोफाइल की गणना करने के लिए वोरोनोई आरेख का उपयोग किया जाता है।

रेफरी>Kasim, Muhammad Firmansyah (2017-01-01). "बड़ी तीव्रता के मॉडुलन के लिए मात्रात्मक छायाचित्रण और प्रोटॉन रेडियोग्राफी". Physical Review E. 95 (2): 023306. arXiv:1607.04179. Bibcode:2017PhRvE..95b3306K. doi:10.1103/PhysRevE.95.023306. PMID 28297858. S2CID 13326345.</रेफरी>

स्वास्थ्य

• चिकित्सीय निदान में, वोरोनोई आरेखों पर आधारित मांसपेशी ऊतक के मॉडल का उपयोग स्नायुपेशीय रोगों का पता लगाने के लिए किया जा सकता है।<रेफरी नाम= सांचेज़-गुतिरेज़ 77–88 />
• महामारी विज्ञान में, वोरोनोई आरेखों का उपयोग महामारी में संक्रमण के स्रोतों को सहसंबंधित करने के लिए किया जा सकता है। वोरोनोई आरेखों के प्रारंभिक अनुप्रयोगों में से एक जॉन स्नो (चिकित्सक) द्वारा सोहो, इंग्लैंड में 1854 ब्रॉड स्ट्रीट हैजा के प्रकोप का अध्ययन करने के लिए लागू किया गया था। उन्होंने मध्य लंदन के मानचित्र पर आवासीय क्षेत्रों के बीच संबंध दिखाया, जिनके निवासी एक विशिष्ट जल पंप का उपयोग कर रहे थे, और प्रकोप के कारण सबसे अधिक मौतों वाले क्षेत्र।

इंजीनियरिंग

• बहुलक भौतिकी में, वोरोनोई आरेखों का उपयोग पॉलिमर की मुक्त मात्रा का प्रतिनिधित्व करने के लिए किया जा सकता है।
• सामग्री विज्ञान में, धातु मिश्र धातुओं में पॉलीक्रिस्टलाइन माइक्रोस्ट्रक्चर को आमतौर पर वोरोनोई टेसेलेशन का उपयोग करके दर्शाया जाता है। द्वीप विकास में, वोरोनोई आरेख का उपयोग व्यक्तिगत द्वीपों की विकास दर का अनुमान लगाने के लिए किया जाता है। ठोस-अवस्था भौतिकी में, विग्नर-समुच्चय्ज़ कोशिका एक ठोस का वोरोनोई टेसलेशन है, और ब्रिलौइन क्षेत्र क्रिस्टल के पारस्परिक (yahoo) स्थान का वोरोनोई टेसलेशन है जिसमें एक अंतरिक्ष समूह की समरूपता होती है।
• विमानन में, वोरोनोई आरेखों को इन-फ़्लाइट डायवर्जन (ETOPS देखें) के लिए निकटतम हवाई क्षेत्र की पहचान करने के लिए समुद्री प्लॉटिंग चार्ट पर आरोपित किया जाता है, क्योंकि एक विमान अपनी उड़ान योजना के माध्यम से आगे बढ़ता है।
• वास्तुकला में, वोरोनोई पैटर्न कला केंद्र गोल्ड कोस्ट के पुनर्विकास के लिए विजेता प्रविष्टि का आधार थे। रेफरी>"गोल्ड कोस्ट सांस्कृतिक परिसर". ARM Architecture.</रेफरी>
• शहरी नियोजन में, फ्रेट लोडिंग जोन सिस्टम का मूल्यांकन करने के लिए वोरोनोई आरेखों का उपयोग किया जा सकता है।

रेफरी>Lopez, C.; Zhao, C.-L.; Magniol, S; Chiabaut, N; Leclercq, L (28 February 2019). "माल लदान क्षेत्र को प्रबंधित करने के उपाय के रूप में ट्रकों की पार्किंग के लिए परिभ्रमण का सूक्ष्म अनुकरण". Sustainability. 11 (5), 1276.</रेफरी>

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

रेफरी>Singh, K.; Sadeghi, F.; Correns, M.; Blass, T. (December 2019). "तन्यता थकान पर सतह खुरदरापन के मॉडल प्रभावों के लिए एक सूक्ष्म संरचना आधारित दृष्टिकोण". International Journal of Fatigue. 129: 105229. doi:10.1016/j.ijfatigue.2019.105229. S2CID 202213370.</रेफरी>

• रोबोटिक्स में, कुछ नियंत्रण रणनीतियाँ और पथ नियोजन एल्गोरिदम

रेफरी>Niu, Hanlin; Savvaris, Al; Tsourdos, Antonios; Ji, Ze (2019). "मानव रहित सतह वाहनों के लिए वोरोनोई-दृश्यता रोडमैप-आधारित पथ योजना एल्गोरिथम" (PDF). The Journal of Navigation. 72 (4): 850–874. doi:10.1017/S0373463318001005. S2CID 67908628.मल्टी-एजेंट सिस्टम के </रेफरी|मल्टी-रोबोट सिस्टम पर्यावरण के वोरोनोई विभाजन पर आधारित हैं। रेफरी>Cortes, J.; Martinez, S.; Karatas, T.; Bullo, F. (April 2004). "मोबाइल सेंसिंग नेटवर्क के लिए कवरेज नियंत्रण". IEEE Transactions on Robotics and Automation. 20 (2): 243–255. doi:10.1109/TRA.2004.824698. ISSN 2374-958X. S2CID 2022860.</रेफरी>

ज्यामिति

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

सूचना विज्ञान

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

नागरिक शास्त्र और योजना

• मेलबोर्न में, सरकारी स्कूल के छात्र हमेशा निकटतम प्राथमिक स्कूल या हाई स्कूल में भाग लेने के पात्र होते हैं, जहाँ वे रहते हैं, जैसा कि एक सीधी रेखा की दूरी से मापा जाता है। स्कूल जोन का नक्शा इसलिए वोरोनोई आरेख है।

बेकरी

• यूक्रेनी पेस्ट्री शेफ दिनारा कास्को अपने मूल केक को आकार देने के लिए 3डी प्रिंटर से बने सिलिकॉन मोल्ड बनाने के लिए वोरोनोई आरेख के गणितीय सिद्धांतों का उपयोग करते हैं।

एल्गोरिदम

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

यह भी देखें

• डेलाउने त्रिभुज
• नक्शा विभाजन
• प्राकृतिक तत्व विधि
• प्राकृतिक पड़ोसी प्रक्षेप
• निकटतम-पड़ोसी प्रक्षेप
• पावर आरेख
• वोरोनी शहर

संदर्भ

• Aurenhammer, Franz; Klein, Rolf; Lee, Der-Tsai (2013). Voronoi Diagrams and Delaunay Triangulations. World Scientific. ISBN 978-9814447638.
• Bowyer, Adrian (1981). "Computing Dirichlet tessellations". Comput. J. 24 (2): 162–166. doi:10.1093/comjnl/24.2.162.
• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000). "7. Voronoi Diagrams". Computational Geometry (2nd revised ed.). Springer. pp. 47–163. ISBN 978-3-540-65620-3. Includes a description of Fortune's algorithm.
• Klein, Rolf (1989). "Abstract Voronoi diagrams and their applications". Computational Geometry and its Applications. Lecture Notes in Computer Science. Vol. 333. Springer. pp. 148–157. doi:10.1007/3-540-50335-8_31. ISBN 978-3-540-52055-9.
• Lejeune Dirichlet, G. (1850). "Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen". Journal für die Reine und Angewandte Mathematik. 1850 (40): 209–227. doi:10.1515/crll.1850.40.209. S2CID 199546675.
• Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (2000). Spatial Tessellations — Concepts and Applications of Voronoi Diagrams (2nd ed.). Wiley. ISBN 0-471-98635-6.
• Reem, Daniel (2009). "An algorithm for computing Voronoi diagrams of general generators in general normed spaces". Proceedings of the Sixth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2009). pp. 144–152. doi:10.1109/ISVD.2009.23. ISBN 978-1-4244-4769-5.
• Reem, Daniel (2011). "The geometric stability of Voronoi diagrams with respect to small changes of the sites". Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG): 254–263. arXiv:1103.4125. Bibcode:2011arXiv1103.4125R. doi:10.1145/1998196.1998234. ISBN 9781450306829. S2CID 14639512.
• Voronoï, Georges (1908a). "Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier mémoire. Sur quelques propriétés des formes quadratiques positives parfaites" (PDF). Journal für die Reine und Angewandte Mathematik. 1908 (133): 97–178. doi:10.1515/crll.1908.133.97. S2CID 116775758.
• Voronoï, Georges (1908b). "Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs" (PDF). Journal für die Reine und Angewandte Mathematik. 1908 (134): 198–287. doi:10.1515/crll.1908.134.198. S2CID 118441072.
• Watson, David F. (1981). "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes". Comput. J. 24 (2): 167–172. doi:10.1093/comjnl/24.2.167.

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

• समतल ज्यामिति)
• एक समुच्चय का विभाजन
• Delaunay त्रिभुज
• अंक शास्त्र
• तकनीकी
• आधा स्थान (ज्यामिति)
• नोड (ग्राफ सिद्धांत)
• परिमित आयामी
• संख्याओं की ज्यामिति
• नॉर्म्ड स्पेस
• जॉन हिमपात (चिकित्सक)
• 1854 ब्रॉड स्ट्रीट हैजा का प्रकोप
• अंतरिक्ष-विज्ञान
• वर्ग (ज्यामिति)
• कटा हुआ ऑक्टाहेड्रॉन
• सरल घन जाली
• चेहरा केंद्रित घन
• शरीर केंद्रित घन
• असली पेड़
• महालनोबिस डिस्टेंस
• चुकता यूक्लिडियन दूरी
• ऑप्टिकल कैरेक्टर मान्यता
• जोन आरेख
• सीधा कंकाल
• कला इतिहास
• जीवविज्ञान
• कोशिका विज्ञान)
• परिस्थितिकी
• आंशिक शुल्क
• शोर अनुपात का संकेत
• खगोल भौतिकी
• कम्प्यूटेशनल तरल सक्रिय
• चिकित्सा निदान
• पदार्थ विज्ञान
• विग्नर-सीट्ज़ सेल
• भौतिक विज्ञान की ठोस अवस्था
• खुदाई
• आधार - सामग्री संकोचन
• गोलाई (वस्तु)
• सबसे बड़ा खाली गोला
• नियामक माप मशीन
• k-निकटतम पड़ोसी एल्गोरिथम
• ध्यान लगा के पढ़ना या सीखना
• प्रयोक्ता इंटरफ़ेस

बाहरी संबंध

• Weisstein, Eric W. "वोरोनोई आरेख". MathWorld.
• Voronoi Diagrams in CGAL, the Computational Geometry Algorithms Library