+- MKLab (https://mklab.gr)
+-- Forum: [INDEX] (https://mklab.gr/forumdisplay.php?fid=1)
+--- Forum: MATHEMATICS (https://mklab.gr/forumdisplay.php?fid=3)
+---- Forum: ARTICLES (https://mklab.gr/forumdisplay.php?fid=13)
+---- Thread: Graham scan [wikipedia] (/showthread.php?tid=455)
Graham scan [wikipedia] - mklabgr - 06-17-2026
Graham scan is a classic computational geometry algorithm used to find the convex hull of a finite set of points in the plane—the smallest convex polygon containing all the points. Introduced by Ronald Graham in 1972, the algorithm first selects the point with the lowest y-coordinate, then sorts all other points by their polar angle relative to it.
It processes the sorted points one by one, maintaining a stack of candidate hull vertices and removing points that would create a clockwise turn, ensuring that only the outer boundary remains. The result is the convex hull listed in counterclockwise order. Graham scan runs in O(n log n) time due to the sorting step, making it one of the most efficient and widely taught algorithms for solving the convex hull problem.
ARTICLE