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.
- Find the point with the lowest y-coordinate (pivot), ties are broken in favor of lower x-coordinate. This step takes O(n) time.
- Sort the remaining points by polar angle in counter-clockwise order around the pivot. This step takes O(n log n) time.
- 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.