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

From Vigyanwiki
No edit summary
m (21 revisions imported from alpha:ग्राहम_स्कैन)
 
(12 intermediate revisions by 2 users not shown)
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डी उत्तल पतवार खोजने के लिए ग्राहम के स्कैन का डेमो।]]'''ग्राहम का स्कैन''' समय जटिलता [[ बिग ओ अंकन |बिग ओ अंकन]] (''एन'' लॉग ''एन'') के साथ विमान में बिंदुओं के सीमित सेट के उत्तल पतवार को खोजने की विधि है। इसका नाम [[रोनाल्ड ग्राहम]] के नाम पर रखा गया है, जिन्होंने 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 प्रश्न में अंकों की संख्या है।


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


== एल्गोरिथम ==
कोण के क्रम में क्रमबद्ध करने के लिए कोण की गणना करने की आवश्यकता नहीं होती है। कोण के किसी भी कार्य का उपयोग करना संभव है जो [[अंतराल (गणित)]] <math>[0,\pi]</math> में मोनोटोनिक है। [[डॉट उत्पाद]] का उपयोग करके कोसाइन की गणना सरलता से की जाती है, या रेखा के ढलान का उपयोग किया जा सकता है। यदि संख्यात्मक परिशुद्धता दांव पर है, तो सॉर्टिंग एल्गोरिदम द्वारा उपयोग किया जाने वाला तुलना कार्य सापेक्ष कोण निर्धारित करने के लिए क्रॉस उत्पाद के संकेत का उपयोग कर सकता है।
[[Image:Graham Scan.svg|frame|right|जैसा कि कोई देख सकता है, पीएबी और एबीसी वामावर्त हैं, किंतु बीसीडी नहीं है। एल्गोरिदम इस स्थिति का पता लगाता है और पहले से चुने गए खंडों को तब तक हटा देता है जब तक कि लिया गया मोड़ वामावर्त (इस स्थितियों में एबीडी) न हो जाए।]]इस एल्गोरिदम में पहला कदम सबसे कम y-निर्देशांक वाला बिंदु ढूंढना है। यदि सेट में एक से अधिक बिंदुओं पर सबसे कम y-निर्देशांक उपस्थित है, तो अभ्यर्थी में से सबसे कम x-निर्देशांक वाले बिंदु को चुना जाना चाहिए। इस बिंदु P पर कॉल करें। यह चरण बिग O नोटेशन (n) लेता है, जहां n प्रश्न में अंकों की संख्या है।


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


कोण के क्रम में क्रमबद्ध करने के लिए कोण की गणना करने की आवश्यकता नहीं होती है। कोण के किसी भी फ़ंक्शन का उपयोग करना संभव है जो [[अंतराल (गणित)]] <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) है, क्योंकि क्रमबद्ध करने का समय वास्तव में उत्तल पतवार की गणना करने के समय पर हावी होता है।


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


अब स्टैक में उत्तल पतवार है, जहां बिंदु वामावर्त उन्मुख हैं और P0 पहला बिंदु है।
फिर परिणाम को <code>stack</code> में संग्रहीत होने दें।<syntaxhighlight>
let points be the list of points                                                                             
let stack = empty_stack()                                                                                   
                                                                                                           
find the lowest y-coordinate and leftmost point, called P0                                                           
sort points by polar angle with P0, if several points have the same polar angle then only keep the farthest
                                                                                                                     
for point in points:                                                                                                     
    # pop the last point from the stack if we turn clockwise to reach this point                                       
    while count stack > 1 and ccw(next_to_top(stack), top(stack), point) <= 0:                                     
        pop stack                                                                                                 
    push point to stack                                                                                         
end                                                                                                                 
</syntaxhighlight>अब स्टैक में उत्तल पतवार है, जहां बिंदु वामावर्त उन्मुख हैं और P0 प्रथम बिंदु है।


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


यह स्यूडोकोड एल्गोरिदम के परिचय से अनुकूलित है।
यह स्यूडोकोड एल्गोरिदम के परिचय से अनुकूलित है।


== टिप्पणियाँ ==
== टिप्पणियाँ ==
The same basic idea works also if the input is sorted on x-coordinate instead of angle, and the hull is computed in two steps producing the upper and the lower parts of the hull respectively. This modification was devised by A. M. Andrew.<ref>{{cite journal|title=Another efficient algorithm for convex hulls in two dimensions|first=A. M.|last=Andrew|journal=Information Processing Letters|year=1979|volume=9|issue=5|pages=216–219|doi=10.1016/0020-0190(79)90072-3}}</ref> It has the same basic properties as Graham's scan.<ref>{{Cite book
यदि मूल विचार तब ही कार्य करता है जब इनपुट को कोण के अतिरिक्त एक्स-समन्वय पर क्रमबद्ध किया जाता है, और पतवार की गणना क्रमशः पतवार के ऊपरी और निचले भागो का निर्माण करते हुए दो चरणों में की जाती है। यह संशोधन ए. एम. एंड्रयू द्वारा तैयार किया गया था।<ref name=":0">{{cite journal|title=Another efficient algorithm for convex hulls in two dimensions|first=A. M.|last=Andrew|journal=Information Processing Letters|year=1979|volume=9|issue=5|pages=216–219|doi=10.1016/0020-0190(79)90072-3}}</ref> इसमें ग्राहम के स्कैन के समान ही मूल गुण हैं।<ref name=":1">{{Cite book
   | last1 = De Berg
   | last1 = De Berg
   | first1 = Mark
   | first1 = Mark
Line 66: Line 61:
   | isbn = 978-3-540-77973-5 }}</ref>
   | isbn = 978-3-540-77973-5 }}</ref>


Graham's original description involved sorting around an interior point of the [[convex hull]], rather than one of its vertices.<ref name=g72/> For the same choice of a pivot point for the sorting algorithm, connecting all of the other points in their sorted order around this point rather than performing the remaining steps of the Graham scan produces a [[star-shaped polygon]], a [[polygonalization]] of the input.<ref>{{cite conference
ग्राहम के मूल विवरण में [[convex hull|उत्तल पतवार]] के किसी शीर्ष के अतिरिक्त उसके आंतरिक बिंदु को छांटना सम्मिलित था।<ref name=g72/> सॉर्टिंग एल्गोरिदम के लिए धुरी बिंदु की समान पसंद के लिए, ग्राहम स्कैन के शेष चरणों को निष्पादित करने के अतिरिक्त इस बिंदु के चारों ओर उनके क्रमबद्ध क्रम में अन्य सभी बिंदुओं को जोड़ने से [[star-shaped polygon|स्टार-आकार का बहुभुज]], इनपुट का [[polygonalization|बहुभुजीकरण]] उत्पन्न होता है।<ref name=":2">{{cite conference
  | last1 = Arkin | first1 = Esther M.
  | last1 = Arkin | first1 = Esther M.
  | last2 = Fekete | first2 = Sándor P.
  | last2 = Fekete | first2 = Sándor P.
Line 88: Line 83:
  | year = 2003}}</ref>
  | year = 2003}}</ref>


The stack technique used in Graham's scan is very similar to that for the [[all nearest smaller values]] problem, and parallel algorithms for all nearest smaller values may also be used (like Graham's scan) to compute convex hulls of sorted sequences of points efficiently.<ref>{{Cite journal|first1=Omer|last1=Berkman|first2=Baruch|last2=Schieber|author2-link=Baruch Schieber|first3=Uzi|last3=Vishkin|author3-link=Uzi Vishkin|title=Optimal double logarithmic parallel algorithms based on finding all nearest smaller values|journal=Journal of Algorithms|volume=14|pages=344–370|year=1993|issue=3|doi=10.1006/jagm.1993.1018|postscript=<!--None-->|citeseerx=10.1.1.55.5669}}.</ref>
ग्राहम के स्कैन में उपयोग की जाने वाली स्टैक विधि [[all nearest smaller values|सभी निकटतम छोटे मानों]] की समस्या के समान है, और सभी निकटतम छोटे मानों के लिए समानांतर एल्गोरिदम का उपयोग बिंदुओं के क्रमबद्ध अनुक्रमों के उत्तल पतवारों की कुशलता से गणना करने के लिए भी किया जा सकता है<ref name=":3">{{Cite journal|first1=Omer|last1=Berkman|first2=Baruch|last2=Schieber|author2-link=Baruch Schieber|first3=Uzi|last3=Vishkin|author3-link=Uzi Vishkin|title=Optimal double logarithmic parallel algorithms based on finding all nearest smaller values|journal=Journal of Algorithms|volume=14|pages=344–370|year=1993|issue=3|doi=10.1006/jagm.1993.1018|postscript=<!--None-->|citeseerx=10.1.1.55.5669}}.</ref> (ग्राहम के स्कैन की तरह)।
==[[संख्यात्मक मजबूती]]==
==[[संख्यात्मक मजबूती|संख्यात्मक सुदृढ़ता]]==


संख्यात्मक मजबूती उन एल्गोरिदम में निपटने के लिए मुद्दा है जो परिमित-स्पष्ट [[तैरनेवाला स्थल]] कंप्यूटर अंकगणित का उपयोग करते हैं। 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>) जिस भी सीमा तक ऐसा करना संभव हो सकता है, तब परिमित परिशुद्धता और अयथार्थ डेटा की समस्याओं को दूर करता है।


==यह भी देखें==
==यह भी देखें==
Line 109: Line 104:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 06:43, 19 October 2023

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

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

एल्गोरिथम

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

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

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

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

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

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

इस के अतिरिक्त, यह निर्धारित करने के लिए कि क्या तीन बिंदु बाएं मोड़ या दाएं मोड़ का गठन करते हैं, दो रेखा खंडों के मध्य वास्तविक कोण की गणना करने की आवश्यकता नहीं है, और वास्तव में केवल सरल अंकगणित के साथ प्राप्त किया जा सकता है। तीन अंक