ग्राहम स्कैन

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

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

एल्गोरिथम

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

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

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

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

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

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

इस के अतिरिक्त, यह निर्धारित करने के लिए कि क्या तीन बिंदु बाएं मोड़ या दाएं मोड़ का गठन करते हैं, दो रेखा खंडों के बीच वास्तविक कोण की गणना करने की आवश्यकता नहीं है, और वास्तव में केवल सरल अंकगणित के साथ प्राप्त किया जा सकता है। तीन अंक $P_{1}=(x_{1},y_{1})$, $P_{2}=(x_{2},y_{2})$ और $P_{3}=(x_{3},y_{3})$ के लिए, दो वेक्टर (ज्यामितीय) ${\overrightarrow {P_{1}P_{2}}}$ और ${\overrightarrow {P_{1}P_{3}}}$ के क्रॉस उत्पाद के z-निर्देशांक की गणना करते है, जो अभिव्यक्ति $(x_{2}-x_{1})(y_{3}-y_{1})-(y_{2}-y_{1})(x_{3}-x_{1})$ द्वारा दिया गया है। यदि परिणाम 0 है, तो बिंदु संरेख हैं; यदि यह सकारात्मक है, तो तीन बिंदु बाएं मोड़ या वामावर्त अभिविन्यास का गठन करते हैं, अन्यथा दाएं मोड़ या दक्षिणावर्त अभिविन्यास (वामावर्त क्रमांकित बिंदुओं के लिए) का गठन करते हैं।

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

समय जटिलता

बिंदुओं को क्रमबद्ध करने में समय जटिलता O(n log n) होती है। चूँकि ऐसा लग सकता है कि लूप की समय जटिलता O(n²) है, क्योंकि प्रत्येक बिंदु के लिए यह जांचने के लिए वापस जाता है कि क्या पिछले बिंदुओं में से कोई दाहिनी ओर मुड़ता है, यह वास्तव में O(n) है, क्योंकि प्रत्येक बिंदु को कुछ अर्थों में अधिकतम दो बार माना जाता है। प्रत्येक बिंदु एक बार बाएं मोड़ में एक बिंदु $(x_{2},y_{2})$ के रूप में प्रकट हो सकता है (क्योंकि एल्गोरिदम इसके बाद अगले बिंदु $(x_{3},y_{3})$ पर आगे बढ़ता है), और दाएँ मोड़ में एक बिंदु $(x_{2},y_{2})$ के रूप में (क्योंकि बिंदु $(x_{2},y_{2})$ हटा दिया जाता है)। इसलिए समग्र समय जटिलता O(n log n) है, क्योंकि क्रमबद्ध करने का समय वास्तव में उत्तल पतवार की गणना करने के समय पर हावी होता है।

स्यूडोकोड

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

फिर परिणाम को stack में संग्रहीत होने दें।

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

अब स्टैक में उत्तल पतवार है, जहां बिंदु वामावर्त उन्मुख हैं और P0 पहला बिंदु है।

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

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

टिप्पणियाँ

यदि मूल विचार तब ही कार्य करता है जब इनपुट को कोण के अतिरिक्त एक्स-समन्वय पर क्रमबद्ध किया जाता है, और पतवार की गणना क्रमशः पतवार के ऊपरी और निचले भागो का निर्माण करते हुए दो चरणों में की जाती है। यह संशोधन ए. एम. एंड्रयू द्वारा तैयार किया गया था। इसमें ग्राहम के स्कैन के समान ही मूल गुण हैं।

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. It has the same basic properties as Graham's scan.

Graham's original description involved sorting around an interior point of the convex hull, rather than one of its vertices. 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.

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.

संख्यात्मक सुदृढ़ता

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

यह भी देखें

• उत्तल पतवार एल्गोरिदम

अग्रिम पठन

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "33.3: Finding the convex hull". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 949–955. ISBN 0-262-03293-7.