वोरोनोई आरेख

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

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

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

सबसे सरल स्थितिया

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

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

${\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 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

Euclidean distance

Manhattan distance

गुण

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

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

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

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

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

उदाहरण

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

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

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

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

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

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

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

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

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

बिंदुओं के दिए गए समुच्चय के लिए S = {p₁, p₂, ..., p_n} सबसे दूर का बिंदु वोरोनोई आरेख समतल को कक्षों में विभाजित करता है जिसमें P का वही बिंदु सबसे दूर का बिंदु है। p के एक बिंदु में सबसे दूर-बिंदु वोरोनोई आरेख में एक कक्ष है यदि और केवल यदि यह p के उत्तल आवरण का शीर्ष है। H = {H₁, H₂, ..., H_k} P का उत्तल आवरण हो; फिर सबसे दूर का बिंदु वोरोनोई आरेख समतल के k कक्षों में एक उपखंड है, H में प्रत्येक बिंदु के लिए एक, इस गुण के साथ कि एक बिंदु q एक साइट h_i के अनुरूप कक्ष में स्थित है। यदि और केवल यदि d(q, h_i) > d(q, p_j) प्रत्येक P_j∈ S के लिये h_i ≠ p_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: डेलोनाय त्रिभुज § अनुप्रयोग

मानविकी

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

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

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

* जीव विज्ञान में, वोरोनोई आरेखों का उपयोग कोशिकाओं (जीव विज्ञान) और हड्डी के माइक्रोआर्किटेक्चर सहित कई विभिन्न जैविक संरचनाओं के मॉडल के लिए किया जाता है। वास्तविक में, वोरोनोई टेसेलेशन जैविक ऊतकों के संगठन को चलाने वाली भौतिक बाधाओं को समझने के लिए एक ज्यामितीय उपकरण के रूप में काम करते हैं <रेफरी नाम = सांचेज़-गुटिएरेज़ 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-NN वर्गीकरण करने के लिए किया जाता है।
• वैश्विक दृश्य पुनर्निर्माण में, जिसमें रैंडम सेंसर साइट्स और अस्थिर जागृत बहना, भूभौतिकीय डेटा और 3डी अशांति डेटा सम्मिलित हैं, वोरोनोई टेसलेशन का उपयोग गहन शिक्षा के साथ किया जाता है।
• उपयोगकर्ता अंतराफलक के विकास में, वोरोनोई पैटर्न का उपयोग किसी दिए गए बिंदु के लिए सर्वश्रेष्ठ परिभ्रमण स्थिति की गणना करने के लिए किया जा सकता है।

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

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

बेकरी

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

कलन विधि

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

डायरेक्ट कलन विधि में संयोग का कलन विधि सम्मिलित है, एक समतल में बिंदुओं के एक समुच्चय से वोरोनोई आरेख उत्पन्न करने के लिए एक बड़ा ओ नोटेशन (N लॉग (N)) कलन विधि।

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

लिंडे-बुज़ो-ग्रे एल्गोरिथम (उर्फ 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