Graham Scan

The convex hull of a set X of points in the plane is the smallest convex polygon that contains all points in X. Graham’s scan is a method of computing the convex hull of a finite set of points in the plane with complexity O(n log n) where n is the number of points.


  1. Find the point with the lowest y-coordinate (pivot), ties are broken in favor of lower x-coordinate. This step takes O(n) time.
  2. Sort the remaining points by polar angle in counter-clockwise order around the pivot. This step takes O(n log n) time.
  3. Push pivot and first two points onto a stack S.

    This step takes O(n) time since each point is considered at most twice, once when it is pushed onto the stack and again if it is popped off the stack.

Thus, the overall time complexity of Graham scan is O(n log n) i.e., it is dominated by the time taken to sort the points.

Take a look at the C++ implementation.

Try your hand at problem GARDENHU, which uses this idea.

Reference: Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s