Editing Graham scan

{{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.

== Algorithm ==
{{uncited-section|date=February 2024}}
[[Image:Graham Scan.svg|frame|right|As one can see, PAB and ABC are counterclockwise, but BCD is not. The algorithm detects this situation and discards previously chosen segments until the turn taken is counterclockwise (ABD in this case).]]

The first step in this algorithm is to find the point with the lowest y-coordinate. If the lowest y-coordinate exists in more than one point in the set, the point with the lowest x-coordinate out of the candidates should be chosen. Call this point ''P''. This step takes [[Big O notation|O]](''n''), where ''n'' is the number of points in question.

Next, the set of points must be sorted in increasing order of the angle they and the point ''P'' make with the x-axis. Any general-purpose [[sorting algorithm]] is appropriate for this, for example [[heapsort]] (which is O(''n'' log ''n'')).

Sorting in order of angle does not require computing the angle.  It is possible to use any function of the angle which is monotonic in the [[Interval (mathematics)|interval]] <math>[0,\pi]</math> .  The cosine is easily computed using the [[dot product]], or the slope of the line may be used. If numeric precision is at stake, the comparison function used by the sorting algorithm can use the sign of the [[cross product]] to determine relative angles.

If several points are of the same angle, either break ties by increasing distance ([[Taxicab geometry|Manhattan]] or [[Chebyshev distance|Chebyshev]] distance may be used instead of [[Euclidean distance|Euclidean]] for easier computation, since the points lie on the same ray), or delete all but the furthest point.

The algorithm proceeds by considering each of the points in the sorted array in sequence. For each point, it is first determined whether traveling from the two points immediately preceding this point constitutes making a left turn or a right turn. If a right turn, the second-to-last point is not part of the convex hull, and lies 'inside' it. The same determination is then made for the set of the latest point and the two points that immediately precede the point found to have been inside the hull, and is repeated until a "left turn" set is encountered, at which point the algorithm moves on to the next point in the set of points in the sorted array minus any points that were found to be inside the hull; there is no need to consider these points again. (If at any stage the three points are collinear, one may opt either to discard or to report it, since in some applications it is required to find all points on the boundary of the convex hull.)

Again, determining whether three points constitute a "left turn" or a "right turn" does not require computing the actual angle between the two line segments, and can actually be achieved with simple arithmetic only. For three points <math>P_1 = (x_1,y_1)</math>, <math>P_2 = (x_2,y_2)</math> and <math>P_3 = (x_3,y_3)</math>, compute the ''z''-coordinate of the [[cross product]] of the two [[Vector (geometric)|vectors]] <math>\overrightarrow{P_1P_2}</math> and <math>\overrightarrow{P_1P_3}</math>, which is given by the expression <math>(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)</math>. If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn" or counter-clockwise orientation, otherwise a "right turn" or clockwise orientation (for counter-clockwise numbered points).

This process will eventually return to the point at which it started, at which point the algorithm is completed and the stack now contains the points on the convex hull in counterclockwise order.

== Time complexity ==
{{uncited-section|date=February 2024}}
Sorting the points has time complexity O(''n'' log ''n''). 
While it may seem that the time complexity of the loop is O(''n''<sup>2</sup>), because for each point it goes back to check if any of the previous points make a "right turn", it is actually O(''n''), because each point is considered at most twice in some sense.
Each point can appear only once as a point <math>(x_2,y_2)</math> in a "left turn" (because the algorithm advances to the next point <math>(x_3,y_3)</math> after that),
and as a point <math>(x_2,y_2)</math> in a "right turn" (because the point <math>(x_2,y_2)</math> is removed). The overall time complexity is therefore O(''n'' log ''n''), since the time to sort dominates the time to actually compute the convex hull.

== Pseudocode ==
The pseudocode below uses a function ccw: ccw > 0 if three points make a counter-clockwise turn, ccw < 0 if clockwise, and ccw = 0 if collinear. (In real applications, if the coordinates are arbitrary real numbers, the function requires exact comparison of floating-point numbers, and one has to beware of numeric singularities for "nearly" collinear points.)

Then let the result be stored in the <code>stack</code>.

 '''let''' points '''be''' the list of points
 '''let''' stack = empty_stack()
 
 '''find''' the lowest y-coordinate and leftmost point, called P0
 '''sort''' points by polar angle with P0, if several points have the same polar angle then only keep the farthest
 
 '''for''' point '''in''' points:
     # pop the last point from the stack if we turn clockwise to reach this point
     '''while''' '''count''' stack > 1 and '''ccw'''(next_to_top(stack), top(stack), point) <= 0:
         '''pop''' stack
     '''push''' point '''to''' stack
 '''end'''

Now the stack contains the convex hull, where the points are oriented counter-clockwise and P0 is the first point.

Here, <code>next_to_top()</code> is a function for returning the item one entry below the top of stack, without changing the stack, and similarly, <code>top()</code> for returning the topmost element.

This pseudocode is adapted from ''[[Introduction to Algorithms]]''.

== Notes ==
The same basic idea works also if the input is sorted on x-coordinate instead of angle, and the hull is computed in two steps producing the upper and the lower parts of the hull respectively. This modification was devised by A. M. Andrew.<ref>{{cite journal|title=Another efficient algorithm for convex hulls in two dimensions|first=A. M.|last=Andrew|journal=Information Processing Letters|year=1979|volume=9|issue=5|pages=216–219|doi=10.1016/0020-0190(79)90072-3}}</ref>  It has the same basic properties as Graham's scan.<ref>{{Cite book
  | last1 = De Berg
  | first1 = Mark
  | last2 = Cheong
  | first2 = Otfried
  | last3 = Van Kreveld
  | first3 = Marc
  | last4 = Overmars
  | first4 = Mark
  | title = Computational Geometry Algorithms and Applications
  | url = https://archive.org/details/computationalgeo00berg_122
  | url-access = limited
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = Berlin
  | year = 2008
  | pages = [https://archive.org/details/computationalgeo00berg_122/page/n12 2]–14
  | doi = 10.1007/978-3-540-77974-2
  | isbn = 978-3-540-77973-5 }}</ref>

Graham's original description involved sorting around an interior point of the [[convex hull]], rather than one of its vertices.<ref name=g72/> For the same choice of a pivot point for the sorting algorithm, connecting all of the other points in their sorted order around this point rather than performing the remaining steps of the Graham scan produces a [[star-shaped polygon]], a [[polygonalization]] of the input.<ref>{{cite conference
 | last1 = Arkin | first1 = Esther M.
 | last2 = Fekete | first2 = Sándor P.
 | last3 = Hurtado | first3 = Ferran
 | last4 = Mitchell | first4 = Joseph S. B.
 | last5 = Noy | first5 = Marc
 | last6 = Sacristán | first6 = Vera
 | last7 = Sethia | first7 = Saurabh
 | editor1-last = Aronov | editor1-first = Boris
 | editor2-last = Basu | editor2-first = Saugata
 | editor3-last = Pach | editor3-first = János
 | editor4-last = Sharir | editor4-first = Micha
 | contribution = On the reflexivity of point sets
 | doi = 10.1007/978-3-642-55566-4_6
 | mr = 2038472
 | pages = 139–156
 | publisher = Springer | location = Berlin
 | series = Algorithms and Combinatorics
 | title = Discrete and Computational Geometry: The Goodman-Pollack Festschrift
 | volume = 25
 | year = 2003| isbn = 978-3-642-62442-1
 }}</ref>

The stack technique used in Graham's scan is very similar to that for the [[all nearest smaller values]] problem, and parallel algorithms for all nearest smaller values may also be used (like Graham's scan) to compute convex hulls of sorted sequences of points efficiently.<ref>{{Cite journal|first1=Omer|last1=Berkman|first2=Baruch|last2=Schieber|author2-link=Baruch Schieber|first3=Uzi|last3=Vishkin|author3-link=Uzi Vishkin|title=Optimal double logarithmic parallel algorithms based on finding all nearest smaller values|journal=Journal of Algorithms|volume=14|pages=344–370|year=1993|issue=3|doi=10.1006/jagm.1993.1018|citeseerx=10.1.1.55.5669}}.</ref>

==Numerical robustness==

[[Numerical robustness]] is an issue to deal with in algorithms that use finite-precision [[floating-point]] computer arithmetic. A 2004 paper analyzed a simple incremental strategy, which can be used, in particular, for an implementation of the Graham scan.<ref name= mkpsy/> The stated goal of the paper was not to specifically analyze the algorithm, but rather to provide a textbook example of what and how may fail due to floating-point computations in [[computational geometry]].<ref name= mkpsy>{{cite journal| doi=10.1016/j.comgeo.2007.06.003 | volume=40 | issue=1 | title=Classroom examples of robustness problems in geometric computations | year=2008 | journal=Computational Geometry | pages=61–78 | last1 = Kettner | first1 = Lutz | last2 = Mehlhorn | first2 = Kurt | last3 = Pion | first3 = Sylvain | last4 = Schirra | first4 = Stefan | last5 = Yap | first5 = Chee| url = http://hal.inria.fr/docs/00/34/43/10/PDF/RevisedClassroomExamples.pdf | doi-access = free }} (An earlier version was reported in 2004 at ESA'2004)</ref> Later D. Jiang and N. F. Stewart<ref>D. Jiang and N. F. Stewart, [http://www.iro.umontreal.ca/~stewart/JiangStewart11page.pdf Backward error analysis in computational geometry] {{Webarchive|url=https://web.archive.org/web/20170809013621/http://www.iro.umontreal.ca/~stewart/JiangStewart11page.pdf |date=2017-08-09 }}, Computational Science and Its Applications - ICCSA 2006 Volume 3980 of the series ''[[Lecture Notes in Computer Science]]'', pp 50–59</ref> elaborated on this and using the [[backward error analysis]] made two primary conclusions. The first is that the convex hull is a [[well-conditioned]] problem, and therefore one may expect algorithms which produce an answer within a reasonable error margin. Second, they demonstrate that a modification of Graham scan which they call Graham-Fortune (incorporating ideas of [[Steven Fortune]] for numeric stability<ref>{{cite book |last=Fortune |first=Steven |chapter=Stable maintenance of point set triangulations in two dimensions |title=30th Annual Symposium on Foundations of Computer Science |volume=30 |pages=494–499 |year=1989 |doi=10.1109/SFCS.1989.63524 |isbn=0-8186-1982-1 |chapter-url=http://www.computer.org/csdl/proceedings/focs/1989/1982/00/063524.pdf |archive-url=https://web.archive.org/web/20130728143644/http://www.computer.org/csdl/proceedings/focs/1989/1982/00/063524.pdf |archive-date=2013-07-28}}</ref>) does overcome the problems of finite precision and inexact data "to whatever extent it is possible to do so".

==See also==
* [[Convex hull algorithms]]

== References ==
{{reflist}}

==Further reading==
* {{Introduction to Algorithms|2|chapter=33.3: Finding the convex hull|pages= 949–955}}

{{DEFAULTSORT:Graham Scan}}
[[Category:Articles with example pseudocode]]
[[Category:Convex hull algorithms]]