ग्राहम स्कैन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Algorithm for computing convex hulls in a set of points}}
{{short description|Algorithm for computing convex hulls in a set of points}}
[[File:GrahamScanDemo.gif|200px|thumb|2डी उत्तल पतवार खोजने के लिए ग्राहम के स्कैन का डेमो।]]'''ग्राहम स्कैन''' समय जटिलता [[ बिग ओ अंकन |बिग ओ अंकन]] (''n'' log ''n'') के साथ विमान में बिंदुओं के सीमित समूह के उत्तल पतवार को खोजने की विधि है। इसका नाम [[रोनाल्ड ग्राहम]] के नाम पर रखा गया है, जिन्होंने 1972 में मूल एल्गोरिदम प्रकाशित किया था।<ref name=g72>{{cite journal | last1 = Graham | first1 = R.L. | year = 1972 | title = एक परिमित तलीय सेट के उत्तल पतवार को निर्धारित करने के लिए एक कुशल एल्गोरिदम| url = http://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf | journal = Information Processing Letters | volume = 1 | issue = 4| pages = 132–133 | doi=10.1016/0020-0190(72)90045-2}}</ref> एल्गोरिथ्म अपनी सीमा के साथ क्रमबद्ध उत्तल पतवार के सभी शीर्षों को ढूंढता है। यह सीमा में अवतलताओं का कुशलतापूर्वक पता लगाने और उन्हें हटाने के लिए स्टैक (अमूर्त डेटा प्रकार) का उपयोग करता है।
[[File:GrahamScanDemo.gif|200px|thumb|2डी उत्तल पतवार खोजने के लिए ग्राहम के स्कैन का डेमो।]]'''ग्राहम स्कैन''' समय समष्टि [[ बिग ओ अंकन |बिग ओ अंकन]] (''n'' log ''n'') के साथ विमान में बिंदुओं के सीमित समूह के उत्तल पतवार को खोजने की विधि है। इसका नाम [[रोनाल्ड ग्राहम]] के नाम पर रखा गया है, जिन्होंने 1972 में मूल एल्गोरिदम प्रकाशित किया था।<ref name=g72>{{cite journal | last1 = Graham | first1 = R.L. | year = 1972 | title = एक परिमित तलीय सेट के उत्तल पतवार को निर्धारित करने के लिए एक कुशल एल्गोरिदम| url = http://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf | journal = Information Processing Letters | volume = 1 | issue = 4| pages = 132–133 | doi=10.1016/0020-0190(72)90045-2}}</ref> एल्गोरिथ्म अपनी सीमा के साथ क्रमबद्ध उत्तल पतवार के सभी शीर्षों को ढूंढता है। यह सीमा में अवतलताओं का कुशलतापूर्वक पता लगाने और उन्हें हटाने के लिए स्टैक (अमूर्त डेटा प्रकार) का उपयोग करता है।
== एल्गोरिथम ==
== एल्गोरिथम ==
[[Image:Graham Scan.svg|frame|right|जैसा कि कोई देख सकता है, पीएबी और एबीसी वामावर्त हैं, किंतु बीसीडी नहीं है। एल्गोरिदम इस स्थिति का पता लगाता है और पहले से चुने गए खंडों को तब तक हटा देता है जब तक कि लिया गया मोड़ वामावर्त (इस स्थितियों में एबीडी) न हो जाए।]]इस एल्गोरिदम में पहला कदम सबसे कम y-निर्देशांक वाला बिंदु ढूंढना है। यदि समूह में एक से अधिक बिंदुओं पर सबसे कम y-निर्देशांक उपस्थित है, तो अभ्यर्थी में से सबसे कम x-निर्देशांक वाले बिंदु को चुना जाना चाहिए। इस बिंदु P पर कॉल करें। यह चरण बिग O नोटेशन (n) लेता है, जहां n प्रश्न में अंकों की संख्या है।
[[Image:Graham Scan.svg|frame|right|जैसा कि कोई देख सकता है, पीएबी और एबीसी वामावर्त हैं, किंतु बीसीडी नहीं है। एल्गोरिदम इस स्थिति का पता लगाता है और पहले से चुने गए खंडों को तब तक हटा देता है जब तक कि लिया गया मोड़ वामावर्त (इस स्थितियों में एबीडी) न हो जाए।]]इस एल्गोरिदम में प्रथम पथ अधिक क्रम y-निर्देशांक वाला बिंदु खोजते है। यदि समूह में एक से अधिक बिंदुओं पर अधिक कम y-निर्देशांक उपस्थित है, तो अभ्यर्थी में से सबसे कम x-निर्देशांक वाले बिंदु को चुना जाना चाहिए। इस बिंदु P पर कॉल करें। यह चरण बिग O नोटेशन (n) प्राप्त करता है, जहां n प्रश्न में अंकों की संख्या है।


इसके बाद, बिंदुओं के समूह को उनके और बिंदु P द्वारा x-अक्ष के साथ बनाए जाने वाले कोण के बढ़ते क्रम में क्रमबद्ध किया जाना चाहिए। कोई भी सामान्य प्रयोजन [[छँटाई एल्गोरिथ्म|सॉर्टिंग एल्गोरिथ्म]] इसके लिए उपयुक्त है, उदाहरण के लिए [[ढेर बनाएं और छांटें|हेप्सोर्ट]] (जो O (''n'' log ''n'' है))।
इसके पश्चात, बिंदुओं के समूह को उनके और बिंदु P द्वारा x-अक्ष के साथ बनाए जाने वाले कोण के बढ़ते क्रम में क्रमबद्ध किया जाना चाहिए। कोई भी सामान्य प्रयोजन [[छँटाई एल्गोरिथ्म|सॉर्टिंग एल्गोरिथ्म]] इसके लिए उपयुक्त है, उदाहरण के लिए [[ढेर बनाएं और छांटें|हेप्सोर्ट]] (जो O (''n'' log ''n'' है))।


कोण के क्रम में क्रमबद्ध करने के लिए कोण की गणना करने की आवश्यकता नहीं होती है। कोण के किसी भी कार्य का उपयोग करना संभव है जो [[अंतराल (गणित)]] <math>[0,\pi]</math> में मोनोटोनिक है। [[डॉट उत्पाद]] का उपयोग करके कोसाइन की गणना सरलता से की जाती है, या रेखा के ढलान का उपयोग किया जा सकता है। यदि संख्यात्मक परिशुद्धता दांव पर है, तो सॉर्टिंग एल्गोरिदम द्वारा उपयोग किया जाने वाला तुलना कार्य सापेक्ष कोण निर्धारित करने के लिए क्रॉस उत्पाद के संकेत का उपयोग कर सकता है।
कोण के क्रम में क्रमबद्ध करने के लिए कोण की गणना करने की आवश्यकता नहीं होती है। कोण के किसी भी कार्य का उपयोग करना संभव है जो [[अंतराल (गणित)]] <math>[0,\pi]</math> में मोनोटोनिक है। [[डॉट उत्पाद]] का उपयोग करके कोसाइन की गणना सरलता से की जाती है, या रेखा के ढलान का उपयोग किया जा सकता है। यदि संख्यात्मक परिशुद्धता दांव पर है, तो सॉर्टिंग एल्गोरिदम द्वारा उपयोग किया जाने वाला तुलना कार्य सापेक्ष कोण निर्धारित करने के लिए क्रॉस उत्पाद के संकेत का उपयोग कर सकता है।


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


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


इस के अतिरिक्त, यह निर्धारित करने के लिए कि क्या तीन बिंदु बाएं मोड़ या दाएं मोड़ का गठन करते हैं, दो रेखा खंडों के बीच वास्तविक कोण की गणना करने की आवश्यकता नहीं है, और वास्तव में केवल सरल अंकगणित के साथ प्राप्त किया जा सकता है। तीन अंक <math>P_1 = (x_1,y_1)</math>, <math>P_2 = (x_2,y_2)</math> और <math>P_3 = (x_3,y_3)</math> के लिए, दो [[वेक्टर (ज्यामितीय)]] <math>\overrightarrow{P_1P_2}</math> और <math>\overrightarrow{P_1P_3}</math> के क्रॉस उत्पाद के z-निर्देशांक की गणना करते है, जो अभिव्यक्ति <math>(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)</math> द्वारा दिया गया है। यदि परिणाम 0 है, तो बिंदु संरेख हैं; यदि यह सकारात्मक है, तो तीन बिंदु बाएं मोड़ या वामावर्त अभिविन्यास का गठन करते हैं, अन्यथा दाएं मोड़ या दक्षिणावर्त अभिविन्यास (वामावर्त क्रमांकित बिंदुओं के लिए) का गठन करते हैं।
इस के अतिरिक्त, यह निर्धारित करने के लिए कि क्या तीन बिंदु बाएं मोड़ या दाएं मोड़ का गठन करते हैं, दो रेखा खंडों के मध्य वास्तविक कोण की गणना करने की आवश्यकता नहीं है, और वास्तव में केवल सरल अंकगणित के साथ प्राप्त किया जा सकता है। तीन अंक <math>P_1 = (x_1,y_1)</math>, <math>P_2 = (x_2,y_2)</math> और <math>P_3 = (x_3,y_3)</math> के लिए, दो [[वेक्टर (ज्यामितीय)|सदिश (ज्यामितीय)]] <math>\overrightarrow{P_1P_2}</math> और <math>\overrightarrow{P_1P_3}</math> के क्रॉस उत्पाद के z-निर्देशांक की गणना करते है, जो अभिव्यक्ति <math>(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)</math> द्वारा दिया गया है। यदि परिणाम 0 है, तो बिंदु संरेख हैं; यदि यह धनात्मक है, तो तीन बिंदु बाएं मोड़ या वामावर्त अभिविन्यास का गठन करते हैं, अन्यथा दाएं मोड़ या दक्षिणावर्त अभिविन्यास (वामावर्त क्रमांकित बिंदुओं के लिए) का गठन करते हैं।


यह प्रक्रिया अंततः उसी बिंदु पर वापस आ जाएगी जहां से यह प्रारंभ हुई थी, जिस बिंदु पर एल्गोरिदम पूरा हो गया है और स्टैक में अब उत्तल पतवार पर वामावर्त क्रम में बिंदु सम्मिलित हैं।
यह प्रक्रिया अंततः उसी बिंदु पर वापस आ जाएगी जहां से यह प्रारंभ हुई थी, जिस बिंदु पर एल्गोरिदम पूरा हो गया है और स्टैक में अब उत्तल पतवार पर वामावर्त क्रम में बिंदु सम्मिलित हैं।


== समय जटिलता ==
== समय समष्टि ==
बिंदुओं को क्रमबद्ध करने में समय जटिलता O(n log n) होती है। चूँकि ऐसा लग सकता है कि लूप की समय जटिलता O(n<sup>2</sup>) है, क्योंकि प्रत्येक बिंदु के लिए यह जांचने के लिए वापस जाता है कि क्या पिछले बिंदुओं में से कोई दाहिनी ओर मुड़ता है, यह वास्तव में O(n) है, क्योंकि प्रत्येक बिंदु को कुछ अर्थों में अधिकतम दो बार माना जाता है। प्रत्येक बिंदु एक बार बाएं मोड़ में एक बिंदु <math>(x_2,y_2)</math> के रूप में प्रकट हो सकता है (क्योंकि एल्गोरिदम इसके बाद अगले बिंदु <math>(x_3,y_3)</math> पर आगे बढ़ता है), और दाएँ मोड़ में एक बिंदु <math>(x_2,y_2)</math> के रूप में (क्योंकि बिंदु <math>(x_2,y_2)</math> हटा दिया जाता है)। इसलिए समग्र समय जटिलता O(n log n) है, क्योंकि क्रमबद्ध करने का समय वास्तव में उत्तल पतवार की गणना करने के समय पर हावी होता है।
बिंदुओं को क्रमबद्ध करने में समय समष्टि O(n log n) होती है। चूँकि ऐसा लग सकता है कि लूप की समय समष्टि O(n<sup>2</sup>) है, क्योंकि प्रत्येक बिंदु के लिए यह जांचने के लिए वापस जाता है कि क्या पिछले बिंदुओं में से कोई दाहिनी ओर मुड़ता है, यह वास्तव में O(n) है, क्योंकि प्रत्येक बिंदु को कुछ अर्थों में अधिकतम दो बार माना जाता है। प्रत्येक बिंदु एक बार बाएं मोड़ में एक बिंदु <math>(x_2,y_2)</math> के रूप में प्रकट हो सकता है (क्योंकि एल्गोरिदम इसके पश्चात अगले बिंदु <math>(x_3,y_3)</math> पर आगे बढ़ता है), और दाएँ मोड़ में एक बिंदु <math>(x_2,y_2)</math> के रूप में (क्योंकि बिंदु <math>(x_2,y_2)</math> हटा दिया जाता है)। इसलिए समग्र समय समष्टि O(n log n) है, क्योंकि क्रमबद्ध करने का समय वास्तव में उत्तल पतवार की गणना करने के समय पर हावी होता है।


== स्यूडोकोड ==
== स्यूडोकोड ==
नीचे दिया गया स्यूडोकोड कार्य <math>ccw                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        </math> का उपयोग करता है: <math>ccw < 0                                                                                                                                                                                                                                                                                                                                                                                                                                    </math>0 यदि तीन बिंदु वामावर्त घुमाते हैं, यदि <math>ccw < 0                                                                                                                                                                                                                                                                                                                                                                                                                                    </math> है तो दक्षिणावर्त घुमाएँ, और यदि ccw = 0 है तो संरेख करते है। (वास्तविक अनुप्रयोगों में, यदि निर्देशांक इच्छानुसार से वास्तविक संख्याएँ हैं, तो कार्य की आवश्यकता होती है फ़्लोटिंग-पॉइंट संख्याओं की स्पष्ट तुलना, और लगभग संरेख बिंदुओं के लिए संख्यात्मक विलक्षणताओं से सावधान रहना रहा जाता है।)
नीचे दिया गया स्यूडोकोड कार्य <math>ccw                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        </math> का उपयोग करता है: यदि <math>ccw < 0                                                                                                                                                                                                                                                                                                                                                                                                                                    </math>0 जो की तीन बिंदु वामावर्त घुमाते हैं, यदि <math>ccw < 0                                                                                                                                                                                                                                                                                                                                                                                                                                    </math> है तो दक्षिणावर्त घुमाएँ, और यदि ccw = 0 है तो संरेख करते है। (वास्तविक अनुप्रयोगों में, यदि निर्देशांक इच्छानुसार से वास्तविक संख्याएँ हैं, तो कार्य की आवश्यकता होती है फ़्लोटिंग-पॉइंट संख्याओं की स्पष्ट तुलना, और लगभग संरेख बिंदुओं के लिए संख्यात्मक विलक्षणताओं से सावधान रहना रहा जाता है।)


फिर परिणाम को <code>stack</code> में संग्रहीत होने दें।<syntaxhighlight>
फिर परिणाम को <code>stack</code> में संग्रहीत होने दें।<syntaxhighlight>
Line 35: Line 35:
     push point to stack                                                                                           
     push point to stack                                                                                           
end                                                                                                                   
end                                                                                                                   
</syntaxhighlight>अब स्टैक में उत्तल पतवार है, जहां बिंदु वामावर्त उन्मुख हैं और P0 पहला बिंदु है।
</syntaxhighlight>अब स्टैक में उत्तल पतवार है, जहां बिंदु वामावर्त उन्मुख हैं और P0 प्रथम बिंदु है।


यहाँ, <code>next_to_top()</code> स्टैक को बदले बिना, आइटम को स्टैक के शीर्ष के नीचे प्रविष्टि में वापस करने का कार्य है, और इसी तरह, <code>top()</code> सर्वोच्च तत्व को वापस करने के लिए है।
जहाँ , <code>next_to_top()</code> स्टैक को परिवर्तन किये बिना, वस्तु को स्टैक के शीर्ष के नीचे प्रविष्टि में वापस करने का कार्य है, और इसी प्रकार, <code>top()</code> सर्वोच्च तत्व को वापस करने के लिए है।


यह स्यूडोकोड एल्गोरिदम के परिचय से अनुकूलित है।
यह स्यूडोकोड एल्गोरिदम के परिचय से अनुकूलित है।
Line 86: Line 86:
==[[संख्यात्मक मजबूती|संख्यात्मक सुदृढ़ता]]==
==[[संख्यात्मक मजबूती|संख्यात्मक सुदृढ़ता]]==


संख्यात्मक सुदृढ़ता उन एल्गोरिदम में निपटने के लिए उद्देश्य है जो परिमित-स्पष्ट [[तैरनेवाला स्थल|फ़्लोटिंग-पॉइंट]] कंप्यूटर अंकगणित का उपयोग करते हैं। 2004 के पेपर में सरल वृद्धिशील रणनीति का विश्लेषण किया गया था, जिसका उपयोग, विशेष रूप से, ग्राहम स्कैन के कार्यान्वयन के लिए किया जा सकता है।<ref name= mkpsy/> पेपर का घोषित लक्ष्य विशेष रूप से एल्गोरिदम का विश्लेषण करना नहीं था, किंतु [[कम्प्यूटेशनल ज्यामिति]] में फ़्लोटिंग-पॉइंट गणनाओं के कारण क्या और कैसे विफल हो सकता है, इसका पाठ्यपुस्तक उदाहरण प्रदान करना था।<ref name= mkpsy>{{cite journal| doi=10.1016/j.comgeo.2007.06.003 | volume=40 | issue=1 | title=ज्यामितीय संगणनाओं में मजबूती की समस्याओं के कक्षा उदाहरण| year=2008 | journal=Computational Geometry | pages=61–78 | last1 = Kettner | first1 = Lutz | last2 = Mehlhorn | first2 = Kurt | last3 = Pion | first3 = Sylvain | last4 = Schirra | first4 = Stefan | last5 = Yap | first5 = Chee| url = http://hal.inria.fr/docs/00/34/43/10/PDF/RevisedClassroomExamples.pdf | doi-access = free }} (An earlier version was reported in 2004 at ESA'2004)</ref> बाद में डी. जियांग और एन.एफ. स्टीवर्ट<ref>D. Jiang and N. F. Stewart, [http://www.iro.umontreal.ca/~stewart/JiangStewart11page.pdf Backward error analysis in computational geometry] {{Webarchive|url=https://web.archive.org/web/20170809013621/http://www.iro.umontreal.ca/~stewart/JiangStewart11page.pdf |date=2017-08-09 }}, Computational Science and Its Applications - ICCSA 2006 Volume 3980 of the series ''[[Lecture Notes in Computer Science]], pp 50-59</ref> इस पर विस्तार से बताया और पिछड़े त्रुटि विश्लेषण का उपयोग करके दो प्राथमिक निष्कर्ष निकाले है। पहला यह है कि उत्तल पतवार अच्छी तरह से वातानुकूलित समस्या है, और इसलिए कोई ऐसे एल्गोरिदम की अपेक्षा कर सकता है जो उचित त्रुटि मार्जिन के अंदर उत्तर उत्पन्न करता है। दूसरा, वे प्रदर्शित करते हैं कि ग्राहम स्कैन का संशोधन जिसे वे ग्राहम-फॉर्च्यून कहते हैं (संख्यात्मक स्थिरता के लिए [[स्टीवन फॉर्च्यून]] के विचारों को सम्मिलित करते हुए<ref>Fortune, S. Stable maintenance of point set triangulations in two dimensions. Proceedings
संख्यात्मक सुदृढ़ता उन एल्गोरिदम में निपटने के लिए उद्देश्य है जो परिमित-स्पष्ट [[तैरनेवाला स्थल|फ़्लोटिंग-पॉइंट]] कंप्यूटर अंकगणित का उपयोग करते हैं। 2004 के पेपर में सरल वृद्धिशील रणनीति का विश्लेषण किया गया था, जिसका उपयोग, विशेष रूप से, ग्राहम स्कैन के कार्यान्वयन के लिए किया जा सकता है।<ref name= mkpsy/> पेपर का घोषित लक्ष्य विशेष रूप से एल्गोरिदम का विश्लेषण करना नहीं था, किंतु [[कम्प्यूटेशनल ज्यामिति]] में फ़्लोटिंग-पॉइंट गणनाओं के कारण क्या और कैसे विफल हो सकता है, इसका पाठ्यपुस्तक उदाहरण प्रदान करना था।<ref name= mkpsy>{{cite journal| doi=10.1016/j.comgeo.2007.06.003 | volume=40 | issue=1 | title=ज्यामितीय संगणनाओं में मजबूती की समस्याओं के कक्षा उदाहरण| year=2008 | journal=Computational Geometry | pages=61–78 | last1 = Kettner | first1 = Lutz | last2 = Mehlhorn | first2 = Kurt | last3 = Pion | first3 = Sylvain | last4 = Schirra | first4 = Stefan | last5 = Yap | first5 = Chee| url = http://hal.inria.fr/docs/00/34/43/10/PDF/RevisedClassroomExamples.pdf | doi-access = free }} (An earlier version was reported in 2004 at ESA'2004)</ref> इसके पश्चात् डी. जियांग और एन.एफ. स्टीवर्ट<ref>D. Jiang and N. F. Stewart, [http://www.iro.umontreal.ca/~stewart/JiangStewart11page.pdf Backward error analysis in computational geometry] {{Webarchive|url=https://web.archive.org/web/20170809013621/http://www.iro.umontreal.ca/~stewart/JiangStewart11page.pdf |date=2017-08-09 }}, Computational Science and Its Applications - ICCSA 2006 Volume 3980 of the series ''[[Lecture Notes in Computer Science]], pp 50-59</ref> इस पर विस्तार से बताया और पिछड़े त्रुटि विश्लेषण का उपयोग करके दो प्राथमिक निष्कर्ष निकाले है। प्रथम तथ्य यह है कि उत्तल पतवार सही प्रकार से वातानुकूलित समस्या है, और इसलिए कोई ऐसे एल्गोरिदम की अपेक्षा कर सकता है जो उचित त्रुटि मार्जिन के अंदर उत्तर उत्पन्न करता है। दूसरा, वे प्रदर्शित करते हैं कि ग्राहम स्कैन का संशोधन जिसे वे ग्राहम-फॉर्च्यून कहते हैं (संख्यात्मक स्थिरता के लिए [[स्टीवन फॉर्च्यून]] के विचारों को सम्मिलित करते हुए<ref>Fortune, S. Stable maintenance of point set triangulations in two dimensions. Proceedings
of the 30th annual IEEE Symposium on Foundations of Computer Science
of the 30th annual IEEE Symposium on Foundations of Computer Science
Vol. 30, 494-499, 1989.</ref>) जिस भी सीमा तक ऐसा करना संभव हो सकता है, तब परिमित परिशुद्धता और अयथार्थ डेटा की समस्याओं को दूर करता है।
Vol. 30, 494-499, 1989.</ref>) जिस भी सीमा तक ऐसा करना संभव हो सकता है, तब परिमित परिशुद्धता और अयथार्थ डेटा की समस्याओं को दूर करता है।

Revision as of 15:49, 27 July 2023

File:GrahamScanDemo.gif
2डी उत्तल पतवार खोजने के लिए ग्राहम के स्कैन का डेमो।

ग्राहम स्कैन समय समष्टि बिग ओ अंकन (n log n) के साथ विमान में बिंदुओं के सीमित समूह के उत्तल पतवार को खोजने की विधि है। इसका नाम रोनाल्ड ग्राहम के नाम पर रखा गया है, जिन्होंने 1972 में मूल एल्गोरिदम प्रकाशित किया था।[1] एल्गोरिथ्म अपनी सीमा के साथ क्रमबद्ध उत्तल पतवार के सभी शीर्षों को ढूंढता है। यह सीमा में अवतलताओं का कुशलतापूर्वक पता लगाने और उन्हें हटाने के लिए स्टैक (अमूर्त डेटा प्रकार) का उपयोग करता है।

एल्गोरिथम

File:Graham Scan.svg
जैसा कि कोई देख सकता है, पीएबी और एबीसी वामावर्त हैं, किंतु बीसीडी नहीं है। एल्गोरिदम इस स्थिति का पता लगाता है और पहले से चुने गए खंडों को तब तक हटा देता है जब तक कि लिया गया मोड़ वामावर्त (इस स्थितियों में एबीडी) न हो जाए।

इस एल्गोरिदम में प्रथम पथ अधिक क्रम y-निर्देशांक वाला बिंदु खोजते है। यदि समूह में एक से अधिक बिंदुओं पर अधिक कम y-निर्देशांक उपस्थित है, तो अभ्यर्थी में से सबसे कम x-निर्देशांक वाले बिंदु को चुना जाना चाहिए। इस बिंदु P पर कॉल करें। यह चरण बिग O नोटेशन (n) प्राप्त करता है, जहां n प्रश्न में अंकों की संख्या है।

इसके पश्चात, बिंदुओं के समूह को उनके और बिंदु P द्वारा x-अक्ष के साथ बनाए जाने वाले कोण के बढ़ते क्रम में क्रमबद्ध किया जाना चाहिए। कोई भी सामान्य प्रयोजन सॉर्टिंग एल्गोरिथ्म इसके लिए उपयुक्त है, उदाहरण के लिए हेप्सोर्ट (जो O (n log n है))।

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

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

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

इस के अतिरिक्त, यह निर्धारित करने के लिए कि क्या तीन बिंदु बाएं मोड़ या दाएं मोड़ का गठन करते हैं, दो रेखा खंडों के मध्य वास्तविक कोण की गणना करने की आवश्यकता नहीं है, और वास्तव में केवल सरल अंकगणित के साथ प्राप्त किया जा सकता है। तीन अंक , और के लिए, दो सदिश (ज्यामितीय) और के क्रॉस उत्पाद के z-निर्देशांक की गणना करते है, जो अभिव्यक्ति द्वारा दिया गया है। यदि परिणाम 0 है, तो बिंदु संरेख हैं; यदि यह धनात्मक है, तो तीन बिंदु बाएं मोड़ या वामावर्त अभिविन्यास का गठन करते हैं, अन्यथा दाएं मोड़ या दक्षिणावर्त अभिविन्यास (वामावर्त क्रमांकित बिंदुओं के लिए) का गठन करते हैं।

यह प्रक्रिया अंततः उसी बिंदु पर वापस आ जाएगी जहां से यह प्रारंभ हुई थी, जिस बिंदु पर एल्गोरिदम पूरा हो गया है और स्टैक में अब उत्तल पतवार पर वामावर्त क्रम में बिंदु सम्मिलित हैं।

समय समष्टि

बिंदुओं को क्रमबद्ध करने में समय समष्टि O(n log n) होती है। चूँकि ऐसा लग सकता है कि लूप की समय समष्टि O(n2) है, क्योंकि प्रत्येक बिंदु के लिए यह जांचने के लिए वापस जाता है कि क्या पिछले बिंदुओं में से कोई दाहिनी ओर मुड़ता है, यह वास्तव में O(n) है, क्योंकि प्रत्येक बिंदु को कुछ अर्थों में अधिकतम दो बार माना जाता है। प्रत्येक बिंदु एक बार बाएं मोड़ में एक बिंदु