for each push operation. In case of GRAHMS SCAN, at least three points (p0, and are never popped from the stack. So in fact, at most 2 p1 pm) m − pop operations are performed. Therefore, the amortized cost of each Iteration of while loop is O(n)/n = O(1). It implies that the overall for for-loop is O(n). The worst case running time of GRAHAM_SCAN is T(n) = O(n) + O(n lg + O(1) + O(n) = O(n lg where = |Q|. n) n), n Correctness of Grahams Scan The correctness of Graham scan lies in two situations. Part 1 deals with nonleft turns. Part 2 deals with left turns. 1: Each point popped from the stack is not a vertex of CH(Q) and Claim lies inside new CH(S). 1 Proof of Claim Suppose that point pj is popped from the stack because angle makes a nonleft turn as shown in the above figure. Since pk pj pi points are ordered in increasing polar angle around anchor there exists p0, a with either in the interior of the triangle or on the p0 pi pk pj triangle ∆ line segment joining and (geometric property). In either case, pi pk point cannot be a vertex of CH(Q). And this completes the proof of pj claim 1.
for each push operation. In case of GRAHMS SCAN, at least three points (p0, p1 and pm) are never popped from the stack. So in fact, at most m − 2 pop operations are performed. Therefore, the amortized cost of each Iteration of while loop is O(n)/n = O(1). It implies that the overall for for-loop is O(n). The worst case running time of GRAHAM_SCAN is T(n) = O(n) + O(n lg n) + O(1) + O(n) = O(n lg n), where n = |Q|. Correctness of Grahams Scan The correctness of Graham scan lies in two situations. Part 1 deals with nonleft turns. Part 2 deals with left turns. Claim 1: Each point popped from the stack is not a vertex of CH(Q) and lies inside new CH(S). Proof of Claim 1 Suppose that point pj is popped from the stack because angle pk pj pi makes a nonleft turn as shown in the above figure. Since points are ordered in increasing polar angle around anchor p0, there exists a triangle ∆ p0 pi pk with pj either in the interior of the triangle or on the line segment joining pi and pk (geometric property). In either case, point pj cannot be a vertex of CH(Q). And this completes the proof of claim 1.