Graham Scan Algorithm to find Convex Hull


(Team) #1

Reading time: 25 minutes | Coding time: 10 minutes

Graham's Scan Algorithm is an efficient algorithm for finding the convex hull of a finite set of points in the plane with time complexity O(N log N). The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently.

This is a companion discussion topic for the original entry at