Convex Hull Algorithms

A visual exploration of computational geometry. How do different algorithms think about the exact same set of points? Watch them visually construct the optimal outer boundary.

Time & Space Complexity

Algorithm	Time Complexity	Space Complexity
Brute Force	$O(n^3)$	$O(1)$
Jarvis March (Gift Wrapping)	$O(n \cdot h)$	$O(1)$
Monotone Chain	$O(n \log n)$	$O(n)$
Graham Scan	$O(n \log n)$	$O(n)$
QuickHull	$O(n \log n) \text{ avg}$	$O(n)$
Divide & Conquer	$O(n \log n)$	$O(n)$
Kirkpatrick-Seidel	$O(n \log h)$	$O(n)$
Chan's Algorithm	$O(n \log h)$	$O(n)$

* Where n is the total number of points, and h is the number of points that end up on the final hull.

Brute Force

Time:

O(n^3)

Space:

O(1)

The absolute baseline. It checks every possible line segment against every other point. An incredibly inefficient but highly educational visualization.

Jarvis March (Gift Wrapping)

Time:

O(n \cdot h)

Space:

O(1)

An output-sensitive algorithm. It sweeps a laser to find the widest right-turn, effectively "wrapping" a string around the outside of the points. Very fast if the hull has few points (small h).

Monotone Chain

Time:

O(n \log n)

Space:

O(n)

The undisputed king of Competitive Programming. It sorts points by X-coordinate, then builds the lower and upper bounds left-to-right. Extremely robust because it completely avoids complex floating-point polar angles.

Graham Scan

Time:

O(n \log n)

Space:

O(n)

The classic algorithm. It finds the lowest point, sorts all other points by their polar angle (like a sweeping radar), and maintains a stack to prune concave turns.

QuickHull

Time:

O(n \log n) \text{ avg}

Space:

O(n)

Similar to QuickSort. It draws a baseline, finds the furthest point to form a triangle, and ruthlessly deletes all points trapped inside. Extremely fast in practice.

Divide & Conquer

Time:

O(n \log n)

Space:

O(n)

"Conquest before Marriage". It divides the points into tiny sub-hulls, solves them, and then uses walking tangent threads to perfectly stitch them together.

Kirkpatrick-Seidel

Time:

O(n \log h)

Space:

O(n)

"Marriage before Conquest". It mathematically predicts the bridging upper tangent before recursing, allowing it to instantly delete massive chunks of points trapped underneath.

Chan's Algorithm

Time:

O(n \log h)

Space:

O(n)

The Holy Grail. The absolute theoretical limit of 2D geometry. It duct-tapes Graham Scan and Jarvis March together, guessing the hull size and dynamically resizing until it snaps perfectly into place.