Graham Scan Algorithm to find Convex Hull

algorithm
computational-geometry
convex-hull
graham-scan

(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 http://iq.opengenus.org/graham-scan-convex-hull/