Editing Graham scan (section)

{{short description|Algorithm for computing convex hulls in a set of points}}
[[File:GrahamScanDemo.gif|200px|thumb|A demo of Graham's scan to find a 2D convex hull]]
'''Graham's scan''' is a method of finding the [[convex hull]] of a finite set of points in the plane with [[time complexity]] [[Big O notation|O]](''n'' log ''n''). It is named after [[Ronald Graham]], who published the original algorithm in 1972.<ref name=g72>{{cite journal | last1 = Graham | first1 = R.L. | year = 1972 | title = An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set | url = http://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf | journal = Information Processing Letters | volume = 1 | issue = 4| pages = 132–133 | doi=10.1016/0020-0190(72)90045-2}}</ref> The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a [[Stack (abstract data type)|stack]] to detect and remove concavities in the boundary efficiently.