v. Convex Hull

Convex Hull

The smallest convex polygon containing all the given points.

The algorithms

Algorithm	Time	Notes
Andrew’s monotone chain	$O(n\log n)$	sort by $x$; the default — simplest, no angles, no precision headaches
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, implementable
Kirkpatrick-Seidel	$O(n\log h)$	optimal output-sensitive, “ultimate”, hard to implement
Melkman	$O(n)$	input must be a simple polyline

$h$ is the number of hull vertices.

Andrew’s monotone chain — write this one

$O(n\log n)$, exact in integers, no angles, no special cases. keepCollinear controls whether collinear boundary points survive on the hull (needed for convex layers and some counting problems).

vector<P> convexHull(vector<P> pts, bool keepCollinear = false) {
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    int n = pts.size();
    if (n <= 2) return pts;
    if (keepCollinear) {
        bool line = true;                              // all points on one line: handle separately
        for (int i = 1; i + 1 < n && line; i++) line = orient(pts[0], pts[n - 1], pts[i]) == 0;
        if (line) return pts;
    }
    auto bad = [&](P a, P b, P p) {                      // should we pop b when adding p?
        int o = orient(a, b, p);
        return keepCollinear ? o < 0 : o <= 0;
    };
    vector<P> h(2 * n);
    int k = 0;
    for (int i = 0; i < n; i++) {                        // lower hull
        while (k >= 2 && bad(h[k - 2], h[k - 1], pts[i])) k--;
        h[k++] = pts[i];
    }
    for (int i = n - 2, lower = k + 1; i >= 0; i--) {     // upper hull
        while (k >= lower && bad(h[k - 2], h[k - 1], pts[i])) k--;
        h[k++] = pts[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 — get it backwards and you either lose required points or produce a hull with redundant vertices that breaks later $O(\log n)$ queries.

Proof: monotone chain is correct

Lower/upper decomposition. Order points by $x$ (ties by $y$). Every hull vertex lies on the lower chain (no polygon point lies strictly below the segment joining it to its hull-neighbours, when scanning left to right) or the upper chain (symmetric, right to left) — this is simply the hull split at its leftmost and rightmost points into its two monotone-in-$x$ halves, which exists for any convex polygon (a line sweeping in $x$ meets the boundary in exactly two points, generically). Building each independently and concatenating (dropping the duplicated shared endpoint) reconstructs the whole hull.

The stack invariant. Process points by increasing $x$, maintaining a stack (array h[0..k)) that is always the correct lower hull of the points seen so far. Adding point $p$: while the last two stack points $a=h[k-2],b=h[k-1]$ together with $p$ make a non-left turn ($\mathrm{orient}(a,b,p)\le 0$), pop $b$. This is correct because:

• If $\mathrm{orient}(a,b,p)\le 0$, then $b$ lies on or above segment $ap$ (since $p$ is further right than both, a right-turn-or-straight at $b$ means $b$ is not strictly below line $ap$), so $b$ cannot be a lower-hull vertex once $p$ is included — any lower hull containing both $a$ and $p$ already lies on or below $b$, making $b$ redundant (interior or on the hull edge $ap$, removed under the strict <=0 rule, kept under <0 only if genuinely needed for collinear counting).
• Popping continues until the turn is a strict left turn (or the stack has fewer than 2 elements), at which point $b$ is confirmed to still be necessary, and $p$ is pushed.
  By induction on the number of points processed, the stack after each step is exactly the lower hull of the prefix: the base case (first two points) is trivial, and the step above preserves it by removing exactly the points that $p$‘s addition makes redundant and no others (a point still convex relative to its neighbours and $p$ is never popped, since popping only triggers on a non-left turn specifically involving the top two elements and the new point).
  The upper hull follows symmetrically, scanning right to left. $■$

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)$ — 07-rotating-calipers
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)$ — 04-polygons
Extreme point in a direction	ternary search on the hull, $O(\log n)$ — 08-convex-polygon-queries
Tangents from an external point	binary search, $O(\log n)$
Distance between two convex polygons	rotating calipers or Minkowski difference — 10-minkowski-sum
Closest pair of hull vertices	not necessarily on the hull — use divide and conquer, 16-closest-pair
Maximum-area triangle	rotating calipers, $O(n^2)$
Convex hull trick (DP)	the upper hull of lines — 14-convex-hull-trick

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 all of these via the early return, the unique call, and the keepCollinear all-on-one-line branch — but only because they 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 (06-dynamic-hull). In contests this is nearly always avoidable:

• insertions only, offline $\to$ sort and rebuild;
• queries offline $\to$ segment tree on time + a rebuilt hull per node;
• only need extreme points $\to$ 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. See 19-3d-geometry.

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 — the same lifting trick as the in-circle predicate.

Graham Scan

Compute the hull by sorting around a fixed pivot by polar angle instead of by $x$. Historically first; monotone chain is simpler to get right, but Graham scan generalises better to “sweep around a point” problems.

Algorithm

1. Find the point with the lowest $y$ (ties: lowest $x$) — guaranteed to be on the hull. Call it the pivot.
2. Sort all other points by angle around the pivot (CCW), breaking ties by distance.
3. Scan in that order, maintaining a stack, popping while the last three points make a non-left turn.

vector<P> grahamScan(vector<P> pts) {
    int n = pts.size();
    if (n < 3) return pts;
    int piv = 0;
    for (int i = 1; i < n; i++)
        if (pts[i].y < pts[piv].y || (pts[i].y == pts[piv].y && pts[i].x < pts[piv].x)) piv = i;
    swap(pts[0], pts[piv]);
    P pivot = pts[0];
    sort(pts.begin() + 1, pts.end(), [&](P a, P b) {
        ll c = cross(pivot, a, b);
        return c != 0 ? c > 0 : norm2(a - pivot) < norm2(b - pivot);
    });
    vector<P> hull;
    for (P p : pts) {
        while (hull.size() >= 2 && cross(hull[hull.size() - 2], hull.back(), p) <= 0) hull.pop_back();
        hull.push_back(p);
    }
    return hull;
}

Proof: Graham scan is correct

The pivot is on the hull. The point with lowest $y$ (ties: lowest $x$) has every other point on or above the horizontal line through it, so no combination of other points can have it in their interior or on an open edge between them — it must be extreme, hence a hull vertex.
The angular sort visits points in hull-boundary order. Sorting by angle around a vertex that is itself extreme means every other point is seen in exactly the angular order they would appear walking CCW around the eventual hull (points cannot be “out of order” relative to a vertex that sees the whole set within a half-plane spanning less than $180°$, which holds here since the pivot is extreme).
The stack invariant is the same one proved for monotone chain above, run once over the full angular sweep instead of twice over the $x$-sweep: after processing the first $i$ sorted points (plus the pivot), the stack holds exactly their hull, by the identical pop-while-non-left-turn argument. $■$

Tested: both convexHull and grahamScan are checked against a brute-force $O(n^3)$ hull (a point is a hull vertex iff some directed line through two points has all others strictly on one side or collinear) on random small point sets, including all-collinear and duplicate-point inputs.

Melkman

Compute the hull of a simple polyline (a non-self-intersecting path) in $O(n)$, online, with no sorting — the extra structure in a spatially-coherent input is exactly enough to drop the $\log$ factor that a general point set needs ($\Omega (n\log n)$, since sorting reduces to hull construction).

Maintain the hull as a deque holding the hull vertices in order, with the same vertex at both ends (so the deque represents a closed polygon). For each new point $v$: if it’s inside the current hull (a left turn with both the front pair and the back pair), skip it; otherwise pop non-left turns from the front and from the back, then push $v$ onto both ends.

void melkmanAdd(deque<P>& D, P v) {
    if (D.size() >= 3 && cross(D[1] - D[0], v - D[0]) > 0 &&
        cross(D[D.size() - 1] - D[D.size() - 2], v - D[D.size() - 2]) > 0)
        return;                                          // inside the hull
    while (D.size() >= 2 && cross(D[1] - D[0], v - D[0]) <= 0) D.pop_front();
    while (D.size() >= 2 && cross(D[D.size() - 1] - D[D.size() - 2], v - D[D.size() - 2]) <= 0) D.pop_back();
    D.push_front(v);
    D.push_back(v);
}

Seeding: start with D = {p0, p0} (the first point duplicated) and call melkmanAdd for every subsequent point, including the second and third — do not hand-build an initial triangle: the pop/push steps in add build it up correctly on their own, and a hand-built 3-vertex seed checks only two of the triangle’s three edges (the front and back pairs), silently admitting points that violate the third, unchecked edge.

Each point is pushed and popped at most a constant number of times, so $O(n)$ total, and the hull is correct after every insertion (online).

Proof: Melkman's algorithm, and why simplicity is required

Maintain the invariant that $D$ (read front to back, minus the duplicated end) is the convex hull of all points processed so far, in CCW order. The inside test is exactly ”$v$ is on the inner side of both the first and last hull edges”, which — because the hull is convex — holds iff $v$ is inside the hull entirely (if $v$ fails the front test it is outside past that edge; if it fails the back test, outside past that edge; if it passes both, it is inside the wedge bounded by them, and since the current hull is exactly that wedge intersected with everything already enforced by the previous insertions, it is inside the whole hull). When $v$ is outside, it must become a new hull vertex, and the vertices it invalidates are exactly a contiguous run at the front and a contiguous run at the back of the deque — not a run in the middle — because the input is a simple polyline: the new point $v$ is adjacent (along the path) to the previously inserted point, so it can only “reach around” the current hull from outside near where the path last was, which by simplicity (no self-crossing) can only be adjacent to the two ends of the current hull chain as seen from the new point’s approach direction. This is what fails for an arbitrary (non-path) point order: an arbitrary next point can invalidate hull vertices in the interior of the deque, which neither end-pop can reach, producing a wrong hull. $■$

Tested against monotone chain on the boundary of random simple polygons (a simple polygon’s boundary is, by definition, a valid simple closed polyline) — fed in polygon order, both produce the same hull vertex set.

When it applies

• Hull of a simple polygon’s boundary — the canonical use.
• Hull of a path/trajectory — GPS traces, robot paths, contour following.
• Preprocessing step — hull of each piece of a polygon before merging.

Convex Layers

Peel the convex hull repeatedly; layer[i] = how many hulls were removed before point $i$ ends up on the hull (the point’s “onion depth”).

vector<int> convexLayers(vector<P> pts) {
    map<P, int> layerOf;
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    vector<P> rest = pts;
    for (int layer = 0; !rest.empty(); layer++) {
        vector<P> hull = convexHull(rest, true);          // keepCollinear: a point ON an edge is this layer
        set<P> on(hull.begin(), hull.end());
        vector<P> next;
        for (P p : rest) { if (on.count(p)) layerOf[p] = layer; else next.push_back(p); }
        rest = next;
    }
    vector<int> res(pts.size());
    for (int i = 0; i < (int)pts.size(); i++) res[i] = layerOf[pts[i]];
    return res;
}

Complexity: $O(n^2\log n)$ worst case (one $O(n\log n)$ hull per layer, up to $O(n)$ layers) — fine for $n$ up to a few thousand. An $O(n{\log }^{2}n)$ algorithm exists (Chazelle) but is rarely needed in contests. Typical uses: “remove the hull $k$ times”, depth of a point in a point set, nested convex polygons.

Proof: convexLayers is correct

By induction on layer: before the loop’s $k$-th iteration, rest is exactly the points of onion-depth $\ge k$ (true for $k=0$, all points). The hull of rest is, by definition of onion peeling, exactly the depth-$k$ points — any point not on this hull is strictly inside it, hence has a strictly smaller enclosing hull available using only points of depth $>k$ still in rest, i.e. depth $\ge k+1$, and any point on this hull cannot be surrounded by the remaining points alone (it’s extreme for this subset), so has depth exactly $k$. Using keepCollinear=true ensures a point lying exactly on a hull edge (not a hull “corner”) is still assigned to this layer rather than left for the next one, matching the usual onion-peeling convention. Removing the depth-$k$ points leaves exactly the depth $\ge k+1$ points, completing the induction. $■$

Chan’s Algorithm

Compute the hull in output-sensitive $O(n\log h)$ time — beating plain $O(n\log n)$ when the hull is small.

The idea: guess $h$, then combine

Chan’s algorithm marries two hull algorithms: Graham scan ($O(n\log n)$, good on small groups) and Jarvis march / gift wrapping ($O(nh)$, output-sensitive but slow per step).

1. Guess a value $m$ for $h$.
2. Partition the $n$ points into $\lceil n/m\rceil$ groups of size $m$. Hull each group with Graham scan: $O\left(\frac{n}{m}\cdot m\log m\right)=O(n\log m)$ total.
3. Run a Jarvis march on the whole point set, but find each next hull vertex by binary searching the tangent from the current point to each small hull — $O(\log m)$ per group, so $O\left(\frac{n}{m}\log m\right)$ per hull step.
4. Stop after $m$ steps. If the hull closed, output it; otherwise $m<h$: double the exponent ($m\leftarrow m^2$, starting from $m=2$) and restart.

Step 3’s “binary search the tangent from a point to a convex polygon” is exactly the tangent routine in Convex Polygon Queries, reused once per group per Jarvis-march step. Chan’s algorithm is rarely hand-rolled in a contest (see the tip below), so it is presented here as the composition of those two already-implemented, already-tested pieces (Graham scan and the tangent search) rather than as new standalone code.

The doubling trick

Start at $m=2$ and square it each round: $m=2^{2^t}$.

Proof: the $O(n\log h)$ bound

Each round with guess $m$ costs $O(n\log m)$ for the grouping step and $O(h^{\prime }\cdot \frac{n}{m}\log m)$ for the Jarvis march, where $h^{\prime }\le m$ is the number of steps taken before success or failure — both $O(n\log m)$. Let $t^{\ast }=\lceil \log \log h\rceil$ be the first round with $m=2^{2^{t^{\ast }}}\ge h$; all earlier rounds fail (since $m<h$ cannot close the hull) and are wasted work. Summing the cost of all rounds $t=0,\dots ,t^{\ast }$:
${\sum }_{t=0}^{t^{\ast }}O\left(n\log 2^{2^t}\right)={\sum }_{t=0}^{t^{\ast }}O(n\cdot 2^t)=O(n\cdot 2^{t^{\ast }+1})=O(n\cdot 2^{\lceil \log \log h\rceil +1})=O(n\log h),$
a geometric series dominated by its last term, since $2^{t^{\ast }}=\Theta (\log h)$. Squaring rather than doubling $m$ is what makes $2^{t^{\ast }}=\Theta (\log h)$ (so the series collapses to $O(n\log h)$); merely doubling $m$ would need $O(\log h)$ rounds each costing $O(n\log m)\le O(n\log h)$, giving a slower $O(n{\log }^{2}h)$. $■$

In a contest

Andrew’s monotone chain, every time. $O(n\log n)$ with $n\le 10^6$ is nothing, and the code is twenty lines of integer arithmetic. Chan’s algorithm is worth knowing for the technique — guess the output size, double (or square) it, pay only for the last guess — not for its constant factor in practice.

The transferable technique

“Guess the output size, run a doubling search, and pay only for the last guess” also gives: output-sensitive 3D hulls, selection with unknown $k$-dependent bounds, and any algorithm whose cost is $f(n,m)$ with $m$ unknown but verifiable after the fact.

Kirkpatrick-Seidel

The “ultimate convex hull algorithm” (1986) — $O(n\log h)$, output-sensitive and optimal, predating Chan’s algorithm by a decade but considerably harder to implement.

The idea: marriage before conquest

Ordinary divide and conquer splits the input, recurses, then merges — and the merge is where hull algorithms lose time. Kirkpatrick and Seidel invert the order: do the “merge” first, so the recursion only ever works on points that will actually contribute. Building the upper hull:

1. Find the median $x$-coordinate in $O(n)$ (median of medians).
2. Find the bridge — the single upper-hull edge crossing the vertical line at the median — in $O(n)$ via a prune-and-search argument (a 2D linear program).
3. The bridge’s endpoints are hull vertices; discard every point below the bridge.
4. Recurse on the surviving points left and right of the median.

Because step 3 discards non-hull points before recursing, the recursion tree has only $O(h)$ leaves.

$T(n,h)=O(n)+T(n_1,h_1)+T(n_2,h_2),h_1+h_2=h-2,$

which solves to $O(n\log h)$ — matching the $\Omega (n\log h)$ lower bound in the algebraic decision tree model, so this (and Chan’s) is optimal.

	Kirkpatrick-Seidel	Chan
Time	$O(n\log h)$	$O(n\log h)$
Technique	prune-and-search, bridge finding	grouping + doubling guess
Needs	median finding, 2D LP	Graham scan + binary search
Implementation	hard	moderate
Extends to 3D	awkwardly	naturally

Chan’s algorithm achieves the same bound with simpler ingredients, which is why people learn that one. Kirkpatrick-Seidel’s lasting contribution is the prune-and-search paradigm itself — spend linear time discarding a constant fraction of the input, then recurse — which also powers median-of-medians selection, Megiddo’s / Seidel’s linear-time LP, Welzl’s minimum enclosing circle, slope selection, and ham-sandwich cuts.