Suppose be the vertex on the top of the stack and Proof of Subclaim pj also be the predecessor of on the stack. pk pj By the choice of and lies above the extension of the p0 p1, pi line As a result, lies on the shaded region. p0 p1. pi By the fact, a left turn occurs at lies below the extension of the pj, pi line joining and As a result lies on the shaded region. pk pj. pi By the fact, occurs later in the sequence than the polar angle pi pj, of is greater than polar angle of thus of lies left of the p0pi p0pj pi line joining points and As a result lies in the shaded region. p0 pj. pi So, the above three propositions imply that is in the shaded region. pi (And we know this corresponds directly to the shaded region of our geometric property.) Therefore, after has been pushed onto the stack, pi the points on stack form a convex polygon. And this completes the proof. Conclusion Since each point popped from the stack is not a vertex of CH(Q) ( by claim 1). And the points on stack always form the vertices of a convex polygon (by claim 2). Therefore, Grahams scan is correct. Applet Graham's scan starts with 25 random points, and then computes their convex hull. The algorithm works in three phases (as mentioned above):
Proof of Subclaim Suppose pj be the vertex on the top of the stack and also pk be the predecessor of pj on the stack. By the choice of p0 and p1, pi lies above the extension of the line p0 p1. As a result, pi lies on the shaded region. By the fact, a left turn occurs at pj, pi lies below the extension of the line joining pk and pj. As a result pi lies on the shaded region. By the fact, pi occurs later in the sequence than pj, the polar angle of p0pi is greater than polar angle of p0pj thus pi of lies left of the line joining points p0 and pj. As a result pi lies in the shaded region. So, the above three propositions imply that pi is in the shaded region. (And we know this corresponds directly to the shaded region of our geometric property.) Therefore, after pi has been pushed onto the stack, the points on stack form a convex polygon. And this completes the proof. Conclusion Since each point popped from the stack is not a vertex of CH(Q) ( by claim 1). And the points on stack always form the vertices of a convex polygon (by claim 2). Therefore, Grahams scan is correct. Applet Graham's scan starts with 25 random points, and then computes their convex hull. The algorithm works in three phases (as mentioned above):
4-graham.docx