Convex Hull — Graham Scan and Jarvis March Algorithms
- Cross product = (B-A) × (C-A): positive = left turn (keep), negative = right turn (pop from stack), zero = collinear (depends on requirements).
- Graham scan: sort by polar angle from pivot, stack-based sweep maintaining left turns. O(n log n). Sort step dominates.
- Jarvis march: always pick most counterclockwise next point from current. O(nh) — faster when hull is tiny (h << log n).
Convex hull is the gateway algorithm to computational geometry. It appears in collision detection (is object A inside the convex hull of object B?), pathfinding (compute the hull to find the shortest path around an obstacle), computer vision (shape descriptors), and machine learning (support vector machine margin computation).
Graham scan and Jarvis march solve the same problem with different trade-offs. Graham scan is O(n log n) regardless of hull size — optimal for large point clouds. Jarvis march is O(nh) where h is the hull output size — better when the hull has very few points (h << log n). Knowing this trade-off and when it matters is what distinguishes thorough geometry knowledge.
The Cross Product — Detecting Left Turns
The foundation of both algorithms is the 2D cross product. For three points p1, p2, p3: cross = (p2.x-p1.x)(p3.y-p1.y) - (p2.y-p1.y)(p3.x-p1.x)
- cross > 0: left turn (counterclockwise) ✓ keep
- cross < 0: right turn (clockwise) ✗ remove
- cross = 0: collinear
def cross(O, A, B): """Cross product of vectors OA and OB. > 0: CCW (left turn), < 0: CW (right turn), = 0: collinear """ return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0]) print(cross((0,0),(1,0),(0,1))) # 1 → left turn print(cross((0,0),(0,1),(1,0))) # -1 → right turn print(cross((0,0),(1,1),(2,2))) # 0 → collinear
-1
0
Graham Scan — O(n log n)
- Find the lowest point (by y, then x) as the pivot
- Sort all other points by polar angle from pivot
- Process points: maintain a stack — pop whenever the top three points make a right turn
from functools import cmp_to_key def graham_scan(points: list[tuple]) -> list[tuple]: points = list(set(points)) if len(points) < 3: return points # Find bottom-left pivot pivot = min(points, key=lambda p: (p[1], p[0])) def compare(a, b): c = cross(pivot, a, b) if c != 0: return -1 if c > 0 else 1 # Collinear: closer point first da = (a[0]-pivot[0])**2 + (a[1]-pivot[1])**2 db = (b[0]-pivot[0])**2 + (b[1]-pivot[1])**2 return -1 if da < db else 1 pts = sorted([p for p in points if p != pivot], key=cmp_to_key(compare)) pts = [pivot] + pts # Graham scan hull = [] for p in pts: while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0: hull.pop() hull.append(p) return hull pts = [(0,0),(1,1),(2,2),(0,2),(2,0),(1,3),(3,1)] print(graham_scan(pts))
Jarvis March (Gift Wrapping) — O(nh)
Start from the leftmost point. Repeatedly pick the point that is most counterclockwise from the current point. Stop when we return to the start.
def jarvis_march(points: list[tuple]) -> list[tuple]: n = len(points) if n < 3: return points # Start from leftmost point start = min(range(n), key=lambda i: points[i]) hull = [] current = start while True: hull.append(points[current]) next_pt = (current + 1) % n for i in range(n): if cross(points[current], points[next_pt], points[i]) > 0: next_pt = i current = next_pt if current == start: break return hull pts = [(0,0),(1,1),(2,2),(0,2),(2,0),(1,3),(3,1)] print(jarvis_march(pts))
Comparison
Graham Scan: O(n log n) regardless of hull size — better for large point clouds where hull is also large. Jarvis March: O(nh) where h = hull points — better when hull is very small (h << log n). Practical choice: Graham Scan is preferred in general. Jarvis March is simpler to remember.
🎯 Key Takeaways
- Cross product = (B-A) × (C-A): positive = left turn (keep), negative = right turn (pop from stack), zero = collinear (depends on requirements).
- Graham scan: sort by polar angle from pivot, stack-based sweep maintaining left turns. O(n log n). Sort step dominates.
- Jarvis march: always pick most counterclockwise next point from current. O(nh) — faster when hull is tiny (h << log n).
- For competitive programming: Graham scan is more commonly correct under all edge cases. Jarvis march can struggle with collinear points if not handled carefully.
- Practical application: convex hull is the preprocessing step for many computational geometry algorithms — diameter, minimum enclosing circle, visibility graphs.
Interview Questions on This Topic
- QWhat does the cross product tell us in the context of convex hull?
- QExplain the stack-based invariant in Graham Scan.
- QWhen is Jarvis March faster than Graham Scan?
- QHow would you handle collinear points in a convex hull algorithm?
Frequently Asked Questions
Does the convex hull include interior points?
No — the hull consists only of the extreme points on the boundary. Interior points and collinear points on edges are typically excluded (or optionally included for edges).
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.