Convex Hull

The smallest convex polygon containing all the given points.

Andrew’s monotone chain — write this one

$O(n\log n)$, exact in integers, no angles, no special cases.

vector<P> convexHull(vector<P> p) {
    int n = p.size();
    if (n <= 2) { sort(p.begin(), p.end()); p.erase(unique(p.begin(), p.end()), p.end()); return p; }
    sort(p.begin(), p.end());                              // by x, then y
    p.erase(unique(p.begin(), p.end()), p.end());
 
    vector<P> h(2 * n);
    int k = 0;
    for (int i = 0; i < (int)p.size(); i++) {              // lower hull
        while (k >= 2 && cross(h[k-2], h[k-1], p[i]) <= 0) k--;
        h[k++] = p[i];
    }
    for (int i = p.size() - 2, t = k + 1; i >= 0; i--) {   // upper hull
        while (k >= t && cross(h[k-2], h[k-1], p[i]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);                                        // drop the duplicated start
    return h;                                               // counter-clockwise
}

<= 0 vs < 0 decides whether collinear points on the hull’s edges are kept:

• <= 0 → strict hull, collinear points removed (usually what you want);
• < 0 → collinear boundary points retained (needed for some counting problems).

Get this wrong and you either lose required points or produce a hull with redundant vertices that breaks later $O(\log n)$ queries.

The algorithms

Algorithm	Time	Notes
Andrew’s monotone chain	$O(n\log n)$	sort by $x$; the default
Graham scan	$O(n\log n)$	sort by angle; more edge cases
Jarvis march (gift wrapping)	$O(nh)$	output-sensitive, simple, slow
QuickHull	$O(n\log n)$ avg, $O(n^2)$ worst	divide and conquer
Chan	$O(n\log h)$	optimal output-sensitive
Kirkpatrick-Seidel	$O(n\log h)$	”ultimate”, complicated
Melkman	$O(n)$	input must be a simple polyline

What the hull unlocks

Once the points are in convex position and ordered, many queries become $O(\log n)$ or $O(n)$:

Query	Method
Diameter (farthest pair)	rotating calipers, $O(n)$
Width (minimum strip)	rotating calipers
Minimum-area enclosing rectangle	rotating calipers — one side lies on a hull edge
Point in convex polygon	binary search, $O(\log n)$
Extreme point in a direction	ternary search on the hull, $O(\log n)$
Tangents from an external point	binary search, $O(\log n)$
Distance between two convex polygons	rotating calipers or Minkowski difference
Closest pair of hull vertices	not necessarily on the hull — use divide and conquer
Maximum-area triangle	rotating calipers, $O(n^2)$
Convex hull trick (DP)	the upper hull of lines — see CHT

Degenerate cases to test

The inputs that break hull code

• $n=1$ and $n=2$
• all points identical
• all points collinear
• duplicate points in the input
• exactly three points, collinear

The monotone chain above handles these via the early return and the unique call — but only because both are there. Test them.

Dynamic convex hull

Maintaining a hull under insertions and deletions needs a balanced BST of hull vertices, $O({\log }^{2}n)$ per update. In contests this is nearly always avoidable:

• insertions only, offline → sort and rebuild;
• queries offline → segment tree on time + a rebuilt hull per node;
• only need extreme points → Li Chao tree on the dual lines.

3D convex hull

The incremental algorithm is $O(n^2)$; randomised incremental with a conflict graph is $O(n\log n)$ expected. Substantially harder than 2D — the output is a set of faces, and degeneracies (coplanar points) are much nastier.

Worth knowing: the 3D hull of points lifted onto a paraboloid $(x,y)\to (x,y,x^2+y^2)$ has a lower hull that projects exactly to the Delaunay triangulation.

See also: Andrew’s Monotone Chain · Rotating Calipers · Minkowski Sum