CoreSource checked

Graham Scan

Computes a convex hull by sorting points by angle and keeping valid turns.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Intermediate
Family: Convex Hull
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 4
Code example: Not ready
Visualization: Ready

Overview

Graham Scan sorts points around an anchor point and uses a stack to remove points that would make an inward turn.

Core Concepts

polar-angle sortorientation teststack hullconvex boundarygeometric calculationgeometric predicatepolygon boundaryconvex hull

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

When to Use

Use Graham Scan when you need to sort points by polar angle.
Use it for convex hull computation with inputs like set of points.
Use it when the problem depends on spatial relationships between points, lines, or shapes.
Use it when the Convex Hull tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when floating-point precision or degenerate cases are not handled.
Avoid it when the required output is not convex hull vertices in order.

What It Does

Sorts points by polar angle
Builds a hull with a turn test

Use Cases

Convex hull computation
Computational geometry teaching
Boundary extraction

Inputs

Set of points

Outputs

Convex hull vertices in order

Key Formulas (1)

Hull turn test

pop while orientation(second_last, last, candidate) ≤ 0

pop while orientation(second_last, last, candidate) <= 0

Removes points that would make the hull turn clockwise or become collinear, depending on the chosen boundary rule.

Pseudocode

1.Choose the lowest point as the anchor
2.Sort other points by angle from the anchor
3.Push points onto a stack
4.Pop while the last turn is not part of the hull
5.Return the stack as the hull

Canonical Example

Input: points = [(0,0), (2,0), (1,1), (1,0)]
Output: spatial result such as a boundary, intersection, or containment answer
Explanation: Graham Scan: The algorithm uses geometric tests to reason about the input shapes.

Implementation Notes

Keep the input contract explicit: Set of points.
Use this step as the implementation spine: Choose the lowest point as the anchor.
Then preserve the next state change: Sort other points by angle from the anchor.
Write tests for points on boundaries, equal coordinates, and very small distances.

Common Pitfalls

Handling duplicate angles and collinear points requires clear tie-breaking.
Forgetting collinear, duplicate, overlapping, or boundary cases.
Returning convex hull vertices in order without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show points being pushed and popped while the hull forms.

Step 1 of 5: Choose the lowest point as the anchor

hull-stack

Notes

Graham Scan operates in O(n log n) time and O(n) space within the Convex Hull family. Key governing relation: pop while orientation(second_last, last, candidate) <= 0. Often compared with Convex Hull and Point in Polygon.