Graham scan
|
|
The Graham scan, named after Ronald Graham, is a method of computing the convex hull of a given set of points in the plane with time complexity O(n log n).
The algorithm
The first step in this algorithm is to find the point with the lowest y-coordinate. If there is a tie, the point with the lowest x-coordinate out of the tie breaking candidates should be chosen. Call this point P. This step takes 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 sort algorithm is appropriate for this, for example heapsort (which is O(n log n)). In order to speed up the calculations, it is not actually necessary to calculate the actual angle these points make with the x-axis; instead, it suffices to calculate the tangent of this angle, which can be done with simple integer arithmetic.
The algorithm proceeds by considering each of the points in the sorted array in sequence. For each point, it is determined whether moving from the two previously considered points to this point is a "left turn" or a "right turn". If it is a "right turn", this means that the second-to-last point is not part of the convex hull and should be removed from consideration. This process is continued for as long as the set of the last three points is a "right turn". As soon as a "left turn" is encountered, the algorithm moves on to the next point in the sorted array. (If at any stage the three points are collinear, it is unimportant whether the middle point is removed or not. Removing it would yield a minimal convex hull, but keeping it in does not invalidate it.)
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 by integer arithmetic only. For three points <math>(x_1,y_1)<math>, <math>(x_2,y_2)<math> and <math>(x_3,y_3)<math>, simply compute the cross product <math>(x_2-x_1)(y_3-y_2)-(y_2-y_1)(x_3-x_2)<math> of the two vectors defined by points <math>(x_1,y_1)<math>, <math>(x_2,y_2)<math> and <math>(x_2,y_2)<math>, <math>(x_3,y_3)<math>. If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn", otherwise a "right turn".
This process will eventually return to the point at which it started, at which point the algorithm is completed and the array now contains the points on the convex hull in anticlockwise order.
Time complexity of the Graham scan
Sorting the points has time complexity O(n log n). While it may seem that the time complexity of the loop is O(n2), 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 only once. Each point considered either terminates the inner loop, or it is removed from the array and thus never considered again. The overall time complexity is therefore O(n log n).