# Graham scan

> algorithm for finding the convex hull of a set of points in the plane

**Wikidata**: [Q914780](https://www.wikidata.org/wiki/Q914780)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/Graham_scan)  
**Source**: https://4ort.xyz/entity/graham-scan

## Summary
Graham scan is a convex-hull algorithm that sorts a set of 2-D points by polar angle and then walks counter-clockwise around them to output the smallest convex polygon that contains every point. It guarantees O(n log n) worst-case time, making it one of the earliest and still most frequently taught methods for computing the convex hull of a finite planar set.

## Key Facts
- **Time complexity**: O(n log n) in the worst case (dominated by the initial polar-angle sort).
- **Named after**: Ronald Graham, the mathematician who published the procedure in 1972.
- **Algorithm class**: Convex-hull algorithm; works only in the plane.
- **Core idea**: Start from the bottom-most point, sort the rest by angle, then scan once while maintaining a stack that always stores the current convex hull.
- **Wikipedia sitelinks**: 16 language editions (ca, de, en, es, fa, fr, he, ko, pl, pt, …).
- **GitHub topic tags**: `graham-scan-algorithm`, `graham-scan`.
- **Freebase ID**: `/m/022_1b` (retired dataset reference).
- **Discontinued Microsoft Academic ID**: 2780353867.

## FAQs
### Q: What is the worst-case running time of Graham scan?
A: O(n log n). The algorithm spends most of its time sorting the points by polar angle; the subsequent single scan is linear.

### Q: Is Graham scan limited to two dimensions?
A: Yes. The method relies on a counter-clockwise (ccw) turn test that is defined only in the plane, so it does not generalize to 3-D or higher.

### Q: How does Graham scan differ from monotone chain (Andrew’s algorithm)?
A: Both run in O(n log n) time, but Graham scan sorts points by polar angle and uses a single stack, whereas monotone chain sorts by x-coordinate and builds the upper and lower chains separately.

### Q: Why must the starting point be the bottom-most (and left-most in a tie) point?
A: That point is guaranteed to be on the convex hull, and using it as the angular origin ensures the remaining points are visited in correct counter-clockwise order.

## Why It Matters
Computing the convex hull is a foundational problem in computational geometry, with applications in pattern recognition, collision detection, path planning, graphics, and statistics. Graham scan delivered the first provably optimal O(n log n) solution simple enough to implement in a few dozen lines of code, making it a staple in textbooks and university courses. Its clarity also demystified the concept of “angle sorting” and stack-based pruning, ideas that reappear in triangulation, visibility, and motion-planning algorithms. Because it is comparison-based, the method is comparison-optimal: any algebraic-decision-tree algorithm needs Ω(n log n) comparisons in the worst case, so Graham scan is asymptotically optimal in that model. Even though faster output-sensitive algorithms exist for special cases, Graham scan remains the default choice when predictable performance and ease of coding are paramount.

## Notable For
- First practical O(n log n) convex-hull algorithm for planar point sets.
- Uses only a single stack, giving it a tiny memory footprint compared with divide-and-conquer methods.
- Still the canonical teaching example for combining sorting with a simple geometric predicate (ccw turn).
- Named after Ronald Graham, linking the algorithm to one of the most prolific discrete mathematicians of the 20th century.
- Serves as a subroutine in more advanced geometric algorithms such of Jarvis’s march (when n is small) and onion peeling.

## Body
### Algorithm Steps
1. **Pivot selection**: Identify the point with the smallest y-coordinate (left-most in a tie). Call it P0.
2. **Polar sort**: Sort the remaining n-1 points by the polar angle they make with P0. If two points share the same angle, keep the farther one and discard nearer duplicates.
3. **Stack initialization**: Push P0 and the first sorted point onto a stack.
4. **Scan**: For every subsequent point Pi, while the angle formed by the top two stack entries and Pi makes a non-left turn, pop the stack. Finally push Pi.
5. **Output**: The stack now contains the vertices of the convex hull in counter-clockwise order, starting and ending at P0.

### Complexity Analysis
- Sorting dominates at O(n log n).
- Each point is pushed and popped at most once, so the scan phase is O(n).
- Total: O(n log n) time and O(n) memory.

### Correctness Sketch
The polar order ensures that any non-left turn corresponds to a reflex vertex that cannot be part of the hull. The invariant maintained is that the stack always stores the hull of the points processed so far, so when the algorithm terminates the stack is exactly the convex hull.

### Limitations
- Requires exact arithmetic or robust ccw tests; nearly collinear points can cause instability with floating-point data.
- Not output-sensitive: it always pays the full sorting cost even when the hull contains only a constant fraction of the points.
- Limited to two dimensions; no natural extension to 3-D exists without replacing the turn test with orientation of tetrahedra.

### Implementation Notes
- Use a cross-product to test left/right turns in integer coordinates, avoiding trigonometry.
- Handle angle ties by distance to keep only the extreme point.
- Many textbooks replace the polar-angle sort with an x-coordinate sort followed by a linear-time merge (Andrew’s monotone chain) to sidestep numerical issues with angles.

## References

1. Freebase Data Dumps. 2013