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).
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 19721. 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.
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 P_1 = (x_1,y_1) , P_2 = (x_2,y_2) and P_3 = (x_3,y_3) , compute the z-coordinate of the cross product of the two vectors \overrightarrow{P_1P_2} and \overrightarrow{P_1P_3} , which is given by the expression (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1) .
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.
The pseudocode below uses a function ccw: ccw > 0 if three points make a counter-clockwise turn, ccw stack . 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) 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. This pseudocode is adapted from Introduction to Algorithms.
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.
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. Later D. Jiang and N. F. Stewart 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 ) does overcome the problems of finite precision and inexact data "to whatever extent it is possible to do so".
See also
Convex hull algorithms
Text derived from https://en.wikipedia.org/w/index.php?oldid=1370509132 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Graham scan” publication date (×1) · confidence 0.95 revision URL