Graham scan
Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n).
It is named after Ronald Graham, who published the original algorithm in 1972.
[1] 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.
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.
Any general-purpose sorting algorithm is appropriate for this, for example heapsort (which is O(n log n)).
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 (Manhattan or Chebyshev distance may be used instead of 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.
If a right turn, the second-to-last point is not part of the convex hull, and lies 'inside' it.
(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.
, compute the z-coordinate of the cross product of the two vectors
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).
Sorting the points has time complexity O(n log n).
in a "left turn" (because the algorithm advances to the next point
(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.)
Here, next_to_top() is a function for returning the item one entry below the top of stack, without changing the stack, and similarly, top() for returning the topmost element.
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.
[3] Graham's original description involved sorting around an interior point of the convex hull, rather than one of its vertices.
[1] 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.
[4] 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.
[5] 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.
[6] 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.
[6] Later D. Jiang and N. F. Stewart[7] 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[8]) does overcome the problems of finite precision and inexact data "to whatever extent it is possible to do so".
