ग्रीडी एम्बेडिंग
वितरित कंप्यूटिंग और ज्यामितीय रेखा-चित्र सिद्धांत में, ग्रीडी एम्बेडिंग दूरसंचार नेटवर्क के नोड्स को निर्देशांक निर्दिष्ट करने की प्रक्रिया होती है जिससे कि नेटवर्क के अंदर संदेशों को क्रम करने के लिए ग्रीडी एल्गोरिदम भौगोलिक मार्ग का उपयोग करने की अनुमति मिल सकती है। यद्यपि वायरलेस सेंसर नेटवर्क में उपयोग के लिए ग्रीडी एम्बेडिंग का प्रस्ताव किया गया है, जिसमें नोड्स के पास पहले से ही भौतिक स्थान में स्थिति होती है, यह उपस्तिथ स्थिति ग्रीडी एम्बेडिंग द्वारा उन्हें दी गई स्थिति से भिन्न हो सकती हैं, जो कुछ स्थितियों में आभासी स्थान में बिंदु हो सकती हैं, अतः उच्च आयाम का या गैर-यूक्लिडियन ज्यामिति में इस अर्थ में, ग्रीडी एम्बेडिंग को रेखा-चित्र चित्रकला के रूप के रूप में देखा जा सकता है, जिसमें अमूर्त रेखा-चित्र (संचार नेटवर्क) ज्यामितीय स्थान में रेखा-चित्र एम्बेडिंग होता है।
भौतिक निर्देशांक का उपयोग करने के अतिरिक्त, आभासी स्थान में निर्देशांक का उपयोग करके भौगोलिक क्रम करने का विचार राव एट अल के कारण होता है।[1] इस प्रकार बाद के विकासों से पता चलता है कि प्रत्येक नेटवर्क में अतिशयोक्तिपूर्ण सतह में संक्षिप्त शीर्ष निर्देशांक के साथ ग्रीडी एम्बेडिंग होती है कि बहुफलकीय रेखा-चित्र सहित कुछ रेखा-चित्र में यूक्लिडियन सतह में ग्रीडी एम्बेडिंग होती है और इकाई डिस्क रेखा-चित्र में मध्यम आयामों के कम खिंचाव कारक यूक्लिडियन स्थानों में ग्रीडी एम्बेडिंग होती है।
परिभाषाएँ
ग्रीडी मार्ग में, स्रोत नोड एस से गंतव्य नोड t तक संदेश मध्यवर्ती नोड्स के माध्यम से चरणों के अनुक्रम द्वारा अपने गंतव्य तक जाता है, जिनमें से प्रत्येक संदेश को निकटतम नोड पर भेजता है, जो t के समीप होता है। यदि संदेश मध्यवर्ती नोड x तक पहुंचता है जिसका कोई निकटतम t के समीप नहीं होता है, तब यह प्रगति नहीं कर सकता है और ग्रीडी मार्ग प्रक्रिया विफल हो जाती है। इस प्रकार ग्रीडी एम्बेडिंग दिए गए रेखा-चित्र को इस संपत्ति के साथ एम्बेड करता है कि इस प्रकार की विफलता असंभव होती है। इस प्रकार, इसे इस गुण के साथ रेखा-चित्र के एम्बेडिंग के रूप में वर्णित किया जा सकता है कि प्रत्येक दो नोड्स x और t के लिए, x का निकटतम y उपस्तिथ होता है जैसे कि d(x,t) > d(y,t), जहां d एम्बेडेड स्थान में दूरी दर्शाता है।[2]
बिना ग्रीडी एम्बेडिंग वाले रेखा-चित्र
प्रत्येक रेखा-चित्र में यूक्लिडियन सतह में ग्रीडी एम्बेडिंग नहीं होती है। इस प्रकार सरल प्रति उदाहरण तारा (रेखा-चित्र सिद्धांत) K1,6 द्वारा दिया गया है, अतः आंतरिक नोड और छह पत्तियों वाला पेड़ (रेखा-चित्र सिद्धांत)[2] जब भी इस रेखा-चित्र को समतल में एम्बेड किया जाता है, तब इसकी कुछ दो पत्तियों को 60 डिग्री या उससे कम का कोण बनाता है, जिससे यह पता चलता है कि इन दो पत्तियों में से कम से कम का निकटतम दूसरे पत्ते के समीप नहीं होता है।
उच्च आयामों के यूक्लिडियन स्थानों में, अधिक रेखा-चित्र में ग्रीडी एम्बेडिंग हो सकती है। उदाहरण के लिए, K1,6 में त्रि-आयामी यूक्लिडियन अंतरिक्ष में ग्रीडी एम्बेडिंग होता है, जिसमें तारे का आंतरिक नोड मूल पर है और पत्तियां प्रत्येक समन्वय अक्ष के साथ इकाई की दूरी पर होती हैं। चूँकि, निश्चित आयाम के प्रत्येक यूक्लिडियन स्थान के लिए, ऐसे रेखा-चित्र होते हैं जिन्हें लालच से एम्बेड नहीं किया जा सकता है। इस प्रकार जब भी संख्या n अंतरिक्ष की चुंबन संख्या समस्या से अधिक होती है, तब रेखा-चित्र K1,n कोई ग्रीडी एम्बेडिंग नहीं होता है।[3]
अतिशयोक्तिपूर्ण और संक्षिप्त एम्बेडिंग
यूक्लिडियन सतह की स्थिति के विपरीत, प्रत्येक नेटवर्क में हाइपरबोलिक सतह में ग्रीडी एम्बेडिंग होती है। इस परिणाम के मूल प्रमाण में, रॉबर्ट क्लेनबर्ग द्वारा, नोड स्थितियों को उच्च परिशुद्धता के साथ निर्दिष्ट करने की आवश्यकता होती थी,[4] किन्तु बाद में यह दिखाया गया था कि, नेटवर्क के फैले हुए पेड़ के भारी पथ अपघटन का उपयोग करके, यह संभव हुआ है कि प्रति बिंदु बिट्स की केवल लघुगणकीय संख्या का उपयोग करके, प्रत्येक नोड को संक्षेप में प्रस्तुत करना संभव होता है।[3] इसके विपरीत, ऐसे रेखा-चित्र उपस्तिथ होते हैं जिनमें यूक्लिडियन सतह में ग्रीडी एम्बेडिंग होते है, किन्तु जिसके लिए ऐसे किसी भी एम्बेडिंग के लिए प्रत्येक बिंदु के कार्टेशियन निर्देशांक के लिए बिट्स की बहुपद संख्या की आवश्यकता होती है।[5][6]
रेखा-चित्र के विशेष वर्ग
पेड़
यूक्लिडियन सतह में ग्रीडी एम्बेडिंग को स्वीकार करने वाले पेड़ों के वर्ग (रेखा-चित्र सिद्धांत) को पूर्ण प्रकार से चित्रित किया गया है और पेड़ की ग्रीडी एम्बेडिंग रैखिक समय में पाया जा सकता है जब वह उपस्तिथ होता है।[7]
अधिक सामान्य रेखा-चित्र के लिए, कुछ ग्रीडी एम्बेडिंग एल्गोरिदम जैसे कि क्लेनबर्ग[4] द्वारा दिए गए रेखा-चित्र का स्पैनिंग पेड़ खोजकर प्रारंभ करते है और फिर स्पैनिंग पेड़ का ग्रीडी एम्बेडिंग का निर्माण करते हैं। इस प्रकार परिणाम आवश्यक रूप से पूरे रेखा-चित्र का ग्रीडी एम्बेडिंग भी होता है। चूँकि, ऐसे रेखा-चित्र उपस्तिथ होते हैं जिनमें यूक्लिडियन सतह में ग्रीडी एम्बेडिंग होते है, किन्तु जिनके लिए किसी भी फैले हुए पेड़ में ग्रीडी एम्बेडिंग नहीं होते है।[8]
समतलीय रेखांकन
पापादिमित्रियोउ & रतज्ज़क (2005) ने अनुमान लगाया गया था कि प्रत्येक बहुफलकीय रेखा-चित्र (3-शिखर-संयुक्त समतलीय रेखा-चित्र, या स्टीनिट्ज़ की प्रमेय के अनुसार समतुल्य उत्तल बहुतल का रेखा-चित्र) में यूक्लिडियन सतह में ग्रीडी एम्बेडिंग होती है।[2] इस प्रकार कैक्टस रेखा-चित्र के गुणों का दोहन करके, लीटन & मोइत्रा (2010) ने अनुमान सिद्ध हुआ था।[8][9] इन रेखा-चित्रों की ग्रीडी एम्बेडिंग को लघुगणकीय रूप से प्रति समन्वय अनेक बिट्स के साथ संक्षेप में परिभाषित किया जा सकता है।[10] चूँकि, इस प्रमाण के अनुसार निर्मित ग्रीडी एम्बेडिंग आवश्यक रूप से समतल एम्बेडिंग नहीं होती हैं, जिससे कि उनमें किनारों के जोड़े के मध्य क्रॉसिंग सम्मिलित हो सकती है। सामान्यतः अधिकतम समतलीय रेखांकन के लिए, जिसमें प्रत्येक फलक त्रिभुज होता है, अतः श्नाइडर के सीधी-रेखा एम्बेडिंग एल्गोरिदम भारित संस्करण में नैस्टर-कुराटोव्स्की-मज़ुरकिविज़ लेम्मा को क्रियान्वित करके ग्रीडी समतलीय एम्बेडिंग पाई जा सकती है।[11][12] इस प्रकार प्रबल पापादिमित्रीउ-रतज्ज़क अनुमान, कि प्रत्येक बहुफलकीय रेखा-चित्र में समतलीय ग्रीडी एम्बेडिंग होती है जिसमें सभी सम्मुख उत्तल होते हैं, अतः वह अप्रमाणित रहता है।[13]
इकाई डिस्क रेखा-चित्र
सामान्यतः बिना तार का यंत्र नियंत्रक नेटवर्क जो ग्रीडी कैक्टस रेखा-चित्र एम्बेडिंग एल्गोरिदम का लक्ष्य होता हैं, उन्हें अधिकांशतः इकाई डिस्क रेखा-चित्र के रूप में मॉडल किया जाता है, चूँकि रेखा-चित्र जिसमें प्रत्येक नोड को इकाई डिस्क के रूप में दर्शाया जाता है और प्रत्येक किनारा गैर-रिक्त चौराहे के साथ डिस्क की जोड़ी से मेल खाता है। इस प्रकार रेखा-चित्र के इस विशेष वर्ग के लिए, बहु लयबद्ध आयाम के यूक्लिडियन स्थान में संक्षिप्त ग्रीडी एम्बेडिंग को खोजना संभव होता है, अतः अतिरिक्त संपत्ति के साथ रेखा-चित्र में दूरियों को एम्बेडिंग में दूरियों द्वारा त्रुटिहीन रूप से अनुमानित किया जाता है, जिससे कि ग्रीडी मार्ग द्वारा अपनाए गए पथ संक्षिप्त होते है।[14]
संदर्भ
- ↑ Rao, Ananth; Ratnasamy, Sylvia; Papadimitriou, Christos H.; Shenker, Scott; Stoica, Ion (2003), "Geographic routing without location information", Proc. 9th ACM Mobile Computing and Networking (MobiCom), pp. 96–108, doi:10.1145/938985.938996.
- ↑ 2.0 2.1 2.2 Papadimitriou, Christos H.; Ratajczak, David (2005), "On a conjecture related to geometric routing", Theoretical Computer Science, 344 (1): 3–14, doi:10.1016/j.tcs.2005.06.022, MR 2178923.
- ↑ 3.0 3.1 Eppstein, D.; Goodrich, M. T. (2011), "Succinct greedy geometric routing using hyperbolic geometry", IEEE Transactions on Computers, 60 (11): 1571–1580, doi:10.1109/TC.2010.257.
- ↑ 4.0 4.1 Kleinberg, R. (2007), "Geographic routing using hyperbolic space", Proc. 26th IEEE International Conference on Computer Communications (INFOCOM 2007), pp. 1902–1909, doi:10.1109/INFCOM.2007.221.
- ↑ Cao, Lei; Strelzoff, A.; Sun, J. Z. (2009), "On succinctness of geometric greedy routing in Euclidean plane", 10th International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN 2009), pp. 326–331, doi:10.1109/I-SPAN.2009.20.
- ↑ Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio (2010), "Succinct greedy drawings do not always exist", Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, pp. 171–182, doi:10.1007/978-3-642-11805-0_17.
- ↑ Nöllenburg, Martin; Prutkin, Roman (2013), "Euclidean greedy drawings of trees", Proc. 21st European Symposium on Algorithms (ESA 2013), arXiv:1306.5224, Bibcode:2013arXiv1306.5224N.
- ↑ 8.0 8.1 Leighton, Tom; Moitra, Ankur (2010), "Some results on greedy embeddings in metric spaces", Discrete and Computational Geometry, 44 (3): 686–705, doi:10.1007/s00454-009-9227-6, MR 2679063.
- ↑ Angelini, Patrizio; Frati, Fabrizio; Grilli, Luca (2010), "An algorithm to construct greedy drawings of triangulations", Journal of Graph Algorithms and Applications, 14 (1): 19–51, doi:10.7155/jgaa.00197, MR 2595019.
- ↑ Goodrich, Michael T.; Strash, Darren (2009), "Succinct greedy geometric routing in the Euclidean plane", Algorithms and Computation: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009, Proceedings, Lecture Notes in Computer Science, vol. 5878, Berlin: Springer, pp. 781–791, arXiv:0812.3893, doi:10.1007/978-3-642-10631-6_79, MR 2792775.
- ↑ Schnyder, Walter (1990), "Embedding planar graphs on the grid", Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138–148.
- ↑ Dhandapani, Raghavan (2010), "Greedy drawings of triangulations", Discrete and Computational Geometry, 43 (2): 375–392, doi:10.1007/s00454-009-9235-6, MR 2579703. See also
- ↑ Nöllenburg, Martin; Prutkin, Roman; Rutter, Ignaz (2016), "On self-approaching and increasing-chord drawings of 3-connected planar graphs", Journal of Computational Geometry, 7 (1): 47–69, arXiv:1409.0315, doi:10.20382/jocg.v7i1a3, MR 3463906.
- ↑ Flury, R.; Pemmaraju, S.V.; Wattenhofer, R. (2009), "Greedy routing with bounded stretch", IEEE INFOCOM 2009, pp. 1737–1745, doi:10.1109/INFCOM.2009.5062093.
