[Math] Graham scan with collinear points

Question

I'm having some trouble understanding the Graham scan algorithm as described in Wikipedia. Particularly, I don't understand how to handle collinear points.

Consider these points as a simple example:

(3, 1)
(2, 3)
(2, 4)
(2, 5)
(3, 7)
(1, 2)
(1, 6)

Plotted into a coordinate system, they look like this:

According to my interpretation of the Graham scan, I first need to find the point P with the lowest y coordinate (and lowest x in case of identical y coordinates). As far as I can tell, that point is (3, 1).

Next, I need to order the other points "in increasing order of the angle they and the point P make with the x-axis". As far as I can tell, the correct order should be:

(3, 1)
(3, 7)
(2, 5)
(2, 4)
(1, 6)
(2, 3)
(1, 2)

The next step is to consider whether triplets of points constitute a left or right turn.

Starting with (3, 1), (3, 7), (2, 5), these make a left turn, so I should keep all three: (3, 1), (3, 7), (2, 5)

Moving on to (3, 7), (2, 5), (2, 4), they also make a left turn, so keep all four: (3, 1), (3, 7), (2, 5), (2, 4)

Next: (2, 5), (2, 4), (1, 6): Right turn, so discard (2, 4). Current points: (3, 1), (3, 7), (2, 5), (1, 6). This isn't right. (2, 5) isn't part of the convex hull – not even of the current subset of points considered so far.

Anyway, for good measure, I'll continue with (2, 5), (1, 6), (2, 3): Left turn, so keep all three: (3, 1), (3, 7), (2, 5), (1, 6), (2, 3).

Moving on: (1, 6), (2, 3), (1, 2): Right turn, so discard (2, 3): Result so far: (3, 1), (3, 7), (2, 5), (1, 6), (1, 2).

There are no further points to consider, so (3, 1), (3, 7), (2, 5), (1, 6), (1, 2) is the result I get.

However, I would have expected the result to be (3, 1), (3, 7), (1, 6), (1, 2) – that is, not including (2, 5).

As far as I've been able to tell so far, this happens when some points are collinear.

Is my interpretation of the Graham scan incorrect? Am I doing something wrong?

Answer 1

I think you've omitted one sentence from the Wikipedia description of Graham's algorithm:

This process is continued for as long as the set of the last three points is a "right turn"

So after correctly discarding point (2, 4) you continue to check if last 3 points make a left or right turn. In your example (3, 1), (3, 7), (2, 5), (1, 6) last 3 points make a right turn so we're discarding (2, 5) and continue with (3, 1), (3, 7), (1, 6).

Further processing would look like this:

• Next is (2,3) last three points (3, 7), (1, 6), (2,3) - left turn.
• Next is (1,2) last three points (1, 6), (2,3), (1,2) - right turn.
  • Discard (2,3) leaving us with (3, 7), (1, 6), (1,2) - left turn.
• End of processing result is: (3, 1), (3, 7), (1, 6), (1, 2).