Search code examples
algorithmconvex-hullgrahams-scan

Checking for a nonleft turn in Graham's scan


Following the description of the Graham's scan algorithm from Cormen's "Introduction to Algorithms" I found out the following note:

By checking for a nonleft turn, rather than just a right turn, this test precludes the possibility of a straight angle at a vertex of the resulting convex hull. We want no straight angles, since no vertex of a convex polygon may be a convex combination of other vertices of the polygon.

Could someone explain please, why we should skip straight angles at vertices of the resulting convex hull? It is not clear why

no vertex of a convex polygon may be a convex combination of other vertices of the polygon


Solution

  • That is true because, by definition, convex hull is the smallest convex set of points that contains the polygon.