---
title: Convex Hull
module: Computational Geometry
moduleNumber: 11
lessonNumber: 2
order: 1102
summary: |
  The convex hull is the smallest convex polygon enclosing a point set — the
  rubber band snapped around the nails. We build it with Andrew's monotone chain,
  sorting by $(x,y)$ and sweeping a lower and upper hull while popping any
  non-left turn via the orientation primitive, in $O(n\log n)$. A reduction from
  sorting shows that bound is optimal, and the hull yields diameter, smallest
  enclosing rectangle, and more through rotating calipers.
topics: [Geometry]
sources:
  - book: CLRS
    ref: "Ch. 33 — Computational Geometry (§33.3)"
  - book: Skiena
    ref: "§ — Convex Hull"
  - book: Erickson
    ref: "Ch. — (geometry)"
practice:
  - title: 'Erect the Fence'
    slug: erect-the-fence
    difficulty: Hard
  - title: 'Maximum Number of Visible Points'
    slug: maximum-number-of-visible-points
    difficulty: Hard
  - title: 'Minimum Area Rectangle II'
    slug: minimum-area-rectangle-ii
    difficulty: Medium
---

The previous lesson gave us one operation: the
**orientation** of an ordered triple of points $A, B, C$, read off the sign of
the [cross product](/algorithms/computational-geometry/geometric-primitives)

$$
(B - A) \times (C - A) = (B_x - A_x)(C_y - A_y) - (B_y - A_y)(C_x - A_x).
$$

A **positive** value means $A \to B \to C$ turns **counterclockwise** (a left
turn), a **negative** value means clockwise (a right turn), and **zero** means
the three points are collinear. That one branch-free, multiplication-only test,
with no divisions, no square roots, and no angles, is the only geometric primitive
this lesson needs. We now use it to solve the foundational problem of computational
geometry: given $n$ points in the plane, find their **convex hull**.

## The problem

> **Definition.** The **convex hull** of a finite point set $P$ is the smallest
> convex polygon that contains every point of $P$. Equivalently, it is the
> intersection of all convex sets containing $P$.

The mental picture is exact and worth keeping: hammer a nail into the plane at
each point, stretch a rubber band wide enough to enclose them all, and let go.
The band snaps taut around the outermost points and traces the hull; the points
it touches are the **hull vertices**, and everything else lands strictly inside.

$$
% caption: The convex hull is the smallest convex polygon enclosing the points
\begin{tikzpicture}[
  every node/.style={circle, fill, inner sep=1.6pt},
  scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  % hull vertices
  \node (a) at (0.0,0.4) {};
  \node (b) at (1.6,-0.4) {};
  \node (c) at (3.8,0.2) {};
  \node (d) at (4.4,2.0) {};
  \node (e) at (2.6,3.2) {};
  \node (f) at (0.4,2.6) {};
  % interior points (plain)
  \node at (1.8,1.2) {};
  \node at (2.6,1.8) {};
  \node at (1.4,2.0) {};
  % hull polygon in accent
  \draw[acc, thick] (a.center) -- (b.center) -- (c.center) -- (d.center)
    -- (e.center) -- (f.center) -- cycle;
\end{tikzpicture}
$$

A hull algorithm must report the vertices in boundary order (say
counterclockwise). The naive approaches are slow: testing each ordered pair to
see whether all other points lie on one side of the line through it identifies
hull _edges_ in $O(n^3)$; gift-wrapping (Jarvis march) pivots from one hull vertex
to the next in $O(nh)$ time, where $h$ is the number of hull vertices, good when
the hull is tiny but $\Theta(n^2)$ when every point is a vertex. We can do
better, and provably best, in $O(n\log n)$.

$$
% caption: Gift-wrapping: from $p$ pick $q$ so every other point lies left of ray $p\to q$
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.5pt},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[dot, label=left:$p$] (p) at (0,0) {};
  \node[dot, label=above:$a$] (a) at (3,2.5) {};
  \node[dot, label=above:$b$] (b) at (4,0.5) {};
  \node[dot, label=above left:$c$] (c) at (2,1.5) {};
  \node[dot, label=right:$q$] (q) at (4,-1) {};
  \draw[dashed, gray] (p) -- (a);
  \draw[dashed, gray] (p) -- (b);
  \draw[dashed, gray] (p) -- (c);
  \draw[acc, very thick, ->] (p) -- (q);
  \node[acc, font=\footnotesize] at (2.4,-1.0) {chosen: all left};
\end{tikzpicture}
$$

Gift-wrapping is worth a concrete step, because it is the most literal statement
of what "on the hull" means. Start at the guaranteed hull vertex $p =$ the lowest
point, and pick the next vertex $q$ as the one that makes _every_ other point fall
to the left of the ray $p \to q$ — equivalently, $q$ is the most clockwise point
seen from $p$. Take $p=(0,0)$ and candidates $a=(3,3)$, $b=(4,1)$, $c=(2,2)$. To
choose between $a$ and $b$, test $\ccw(p, a, b) = 3\cdot 1 - 3\cdot 4 = -9 < 0$:
$b$ is a right turn from $p\to a$, i.e. more clockwise, so $b$ beats $a$. Testing
$b$ against $c$ gives $\ccw(p, b, c) = 4\cdot 2 - 1\cdot 2 = 6 > 0$,
so $c$ is a left turn and $b$ still wins. After one full pass $b$ is the most
clockwise, so $b$ is the next hull vertex, and we wrap again from $b$. Each vertex
costs a full $O(n)$ pass, which is why the total is $O(nh)$ — cheap when the hull
is small, quadratic when every point is a corner.

::impl{algo="jarvis_march"}

## Andrew's monotone chain

The cleanest $O(n\log n)$ algorithm sorts the points once and sweeps them with a
stack, building the boundary in two passes.

> **Idea.** Sort the points by $(x, y)$ — primarily by $x$, breaking ties by $y$.
> Sweep **left to right** to build the **lower hull**, then **right to left** to
> build the **upper hull**. In each sweep, maintain the invariant that the points
> currently on the stack make _only counterclockwise turns_. Before pushing a new
> point, **pop** the top of the stack while the last three points fail to turn
> left. Concatenating the two chains closes the polygon.

The pop condition is pure orientation. Suppose the stack ends in $A, B$ and we are
about to add $C$. If $A \to B \to C$ is a left turn (cross product $> 0$), $B$ is
a genuine corner of the hull-so-far and we keep it. If it is a right turn or
collinear (cross product $\le 0$), then $B$ is "inside" the corner that $C$ opens
up (the rubber band would not touch $B$), so we pop $B$ and re-test with the new
top. This is the rejection drawn below.

$$
% caption: Pop while the last three points don't turn counterclockwise
\begin{tikzpicture}[
  >=stealth, scale=1.0,
  pt/.style={circle, fill, inner sep=1.8pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[pt] (A) at (0,0) {};
  \node[pt, fill=red!75!black] (B) at (2.0,1.4) {};
  \node[pt] (C) at (4.2,0.5) {};
  \node[below left] at (A) {$A$};
  \node[above, red!75!black] at (B.north) {$B$ (popped)};
  \node[below right] at (C) {$C$};
  % rejected edges through B (right turn): red, dashed
  \draw[dashed, thick, red!75!black] (A.center) -- (B.center);
  \draw[dashed, thick, red!75!black] (B.center) -- (C.center);
  % corrected hull edge A -> C in accent (the kept left turn)
  \draw[acc, very thick, ->] (A.center) -- (C.center);
\end{tikzpicture}
$$

Here $A \to B \to C$ bends to the **right**, so the chain dips below the convex
boundary at $B$. The algorithm pops $B$ and the corrected edge runs straight from
$A$ to $C$, restoring the all-left-turns invariant.

Inside the left-to-right sweep this plays out as a stack that grows and
occasionally collapses. Below, the stack holds $p_1 p_2 p_3$ when $p_4$ arrives;
the turn at $p_3$ is a right turn, so $p_3$ pops, and now the turn at $p_2$ is
still a right turn, so $p_2$ pops too, leaving the taut chain $p_1 p_4$.

$$
% caption: One sweep step: $p_4$ arrives and cascades two pops, $p_3$ then $p_2$, leaving
%          the lower chain taut
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.5pt},
  >=stealth, scale=0.9]
  \definecolor{acc}{HTML}{2348F2}
  % BEFORE: stack p1 p2 p3, then p4 incoming
  \node[dot, label=below left:$p_1$] (q1) at (0,0)    {};
  \node[dot, label=above:$p_2$]      (q2) at (1.3,1.1){};
  \node[dot, label=above:$p_3$]      (q3) at (2.8,1.5){};
  \node[dot, label=below right:$p_4$](q4) at (4.4,0.3){};
  % current stacked chain (before p4 processed) — discarded, so thin red dashed
  \draw[red!75!black, thin, dashed] (q1.center) -- (q2.center) -- (q3.center);
  % p4 about to be added: dashed grey lead-in
  \draw[dashed, black] (q3.center) -- (q4.center);
  % the popped vertices marked red, the cascade arrow
  \node[dot, fill=red!75!black] at (q2) {};
  \node[dot, fill=red!75!black] at (q3) {};
  \node[red!75!black, font=\footnotesize, align=center] at (2.0,2.35)
    {$p_3$ $p_2$ pop\\(\texttt{right} turns)};
  \draw[red!75!black, ->, thick] (1.7,2.0) to[bend right=12] (1.45,1.35);
  \draw[red!75!black, ->, thick] (2.35,2.05) to[bend left=10] (2.75,1.7);
  % AFTER: corrected chain p1 -> p4
  \draw[acc, very thick, ->] (q1.center) -- (q4.center);
  \node[acc, font=\footnotesize] at (2.6,-0.5) {kept: $p_1 p_4$};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Monotone-Chain}(P)$ — convex hull of points $P$ in $O(n\log n)$
sort $P$ ascending by $(x, y)$, removing duplicates
$L \gets [\,]$ // lower hull
for each point $p$ in $P$ (left to right) do
  while $|L| \ge 2$ and $\text{cross}(L_{-2}, L_{-1}, p) \le 0$ do
    pop $L$
  push $p$ onto $L$
$U \gets [\,]$ // upper hull
for each point $p$ in $P$ (right to left) do
  while $|U| \ge 2$ and $\text{cross}(U_{-2}, U_{-1}, p) \le 0$ do
    pop $U$
  push $p$ onto $U$
drop the last element of $L$ and of $U$ // shared endpoints
return $L$ concatenated with $U$ // counterclockwise
```

Here $L_{-1}, L_{-2}$ denote the top two stack elements and
$\text{cross}(A, B, C)$ is the orientation value above. The last point of each
chain is the first point of the other (the global min and max under the sort
order), so we drop one copy of each to avoid duplicating the two extreme
vertices.

> **Correctness.** After the left-to-right sweep, $L$ traces the lower
> boundary: every consecutive triple turns counterclockwise (the loop guarantees
> it), and no point lies below the chain, because any point we popped was strictly
> above the segment that replaced it. The symmetric claim holds for $U$. A polygon
> whose every interior angle is a left turn is convex, and it contains all points
> since none lies below the lower chain or above the upper chain. $\qed$

**A worked lower-hull sweep.** Take the six points
$A(0,0)$, $B(1,2)$, $C(2,1)$, $D(3,3)$, $E(4,0)$, $F(5,2)$, already sorted by $x$.
The left-to-right sweep builds the lower chain $L$ as a stack; each row is the
stack after processing one point, with the `cross` test that fired.

| point | test at the top two | action | stack $L$ |
| :--- | :--- | :--- | ---: |
| $A$ | — | push | $A$ |
| $B$ | — | push | $A,B$ |
| $C$ | $\text{cross}(A,B,C)=-3<0$ | pop $B$, push $C$ | $A,C$ |
| $D$ | $\text{cross}(A,C,D)=+3>0$ | push | $A,C,D$ |
| $E$ | $\text{cross}(C,D,E)=-5<0$, then $\text{cross}(A,C,E)=-4<0$ | pop $D$, pop $C$, push $E$ | $A,E$ |
| $F$ | $\text{cross}(A,E,F)=+8>0$ | push | $A,E,F$ |

The lower hull is $A,E,F$: the sweep discarded $B$ (a right turn at $A\!-\!B\!-\!C$),
kept $C,D$ tentatively, then evicted both when $E$ arrived and the chain
straightened. The upper-hull pass runs the mirror sweep right to left and closes
the polygon.

**Complexity.** The [sort](/algorithms/sorting/heaps-and-heapsort) costs $\Theta(n\log n)$. Each sweep is linear despite the
inner `while`: a point is pushed once and popped at most once, so the total number
of pop operations across a sweep is at most $n$. The work after sorting is
therefore $\Theta(n)$, and the sort dominates: $O(n\log n)$ overall.

$$
% caption: Monotone chain builds the lower chain ($x$ increasing) then the upper chain
%          back
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.5pt},
  >=stealth, scale=0.95]
  \definecolor{acc}{HTML}{2348F2}
  \node[dot, label=left:$A$]  (A) at (0,1)   {};
  \node[dot, label=below:$B$] (B) at (2,0)   {};
  \node[dot, label=below:$C$] (C) at (5,0.3) {};
  \node[dot, label=right:$D$] (D) at (6,2)   {};
  \node[dot, label=above:$E$] (E) at (4,3.2) {};
  \node[dot, label=above:$F$] (F) at (1,3)   {};
  \node[dot, fill=black!45] at (2,1.5)   {};
  \node[dot, fill=black!45] at (3,2)     {};
  \node[dot, fill=black!45] at (3.5,1)   {};
  \draw[acc, very thick] (A) -- (B) -- (C) -- (D);
  \draw[acc, very thick, dashed] (D) -- (E) -- (F) -- (A);
  \node[acc, font=\footnotesize] at (3.3,-0.55) {lower chain};
  \node[acc, font=\footnotesize] at (3.0,3.75) {\texttt{upper} chain};
\end{tikzpicture}
$$

::impl{algo="monotone_chain,hull_geometry"}

## Graham scan: the classic alternative

The original $O(n\log n)$ hull algorithm, **Graham's scan**, has the same skeleton
but a different ordering. Pick the point with the lowest $y$-coordinate (ties
broken by $x$) as a pivot $p_0$; it is certainly a hull vertex. Sort the remaining
points by **polar angle** around $p_0$, then scan them in that angular order,
maintaining a stack and popping whenever the last three points fail to turn left,
the identical orientation test. Because the points are visited in angular order,
one pass suffices to trace the whole boundary, again in $O(n\log n)$.[^clrs-graham]
$$
% caption: Graham scan sorts the other points by polar angle around the lowest point
%          $p_0$; the scan then walks them counterclockwise, popping right turns.
\begin{tikzpicture}[
  every node/.style={font=\footnotesize},
  dot/.style={circle, fill, inner sep=1.6pt},
  >=stealth, scale=0.95]
  \definecolor{acc}{HTML}{2348F2}
  % pivot p0 lowest, others sorted by increasing angle
  \node[dot, label=below:{$p_0$}] (p0) at (1.0,0) {};
  \node[dot, label=right:{$p_1$}] (p1) at (4.2,0.5) {};
  \node[dot, label=right:{$p_2$}] (p2) at (3.6,2.1) {};
  \node[dot, label=above:{$p_3$}] (p3) at (2.4,3.0) {};
  \node[dot, label=left:{$p_4$}]  (p4) at (0.4,2.4) {};
  % angle rays from p0 in sorted order (dashed, muted)
  \foreach \p in {p1,p2,p3,p4} \draw[black, dashed] (p0) -- (\p);
  % one clean angle arc from the p0->p1 baseline sweeping up through p4
  \draw[acc, ->] (2.6,0) arc (0:78:1.6);
  \node[acc, anchor=west] at (4.4,1.5) {angles increase};
  % the hull traced so far
  \draw[acc, very thick] (p0) -- (p1) -- (p2) -- (p3) -- (p4) -- cycle;
\end{tikzpicture}
$$

Monotone chain is usually preferred in practice precisely because it avoids the
polar-angle sort: comparing $(x, y)$ lexicographically uses only the coordinates,
whereas sorting by angle requires either $\atanTwo$ (floating point,
slow, imprecise) or cross-product comparisons with careful handling of the pivot,
which means more code and more numerical fragility for the same asymptotics.

::impl{algo="graham_scan"}

## Degeneracies

Real inputs are not in "general position," and the hull is where edge cases bite.

- **Duplicate points** must be removed first (the sort makes this a linear scan);
  a repeated point can otherwise wedge a zero-length edge into the chain and break
  the turn test.
- **Collinear points on a hull edge** are a deliberate policy choice, and it lives
  entirely in the comparison operator. Using $\le 0$ in the pop condition (as
  above) **discards** collinear points, keeping only true corners — the minimal
  vertex set. Using $< 0$ **keeps** collinear points on the boundary, so a flat
  edge with interior points reports all of them. Problems like _Erect the Fence_,
  which ask for _every_ point lying on the fence, want the $< 0$ variant; most
  geometry that follows (diameter, area) wants the lean $\le 0$ hull. Decide which
  one your caller needs and pick the inequality accordingly.

For example, suppose the bottom edge of the hull runs
through $A(0,0)$, $M(2,0)$, $B(4,0)$ — three points on one horizontal line, with
$M$ strictly between the corners. When the sweep has $A, M$ on the stack and $B$
arrives, $\cross(A, M, B) = 2\cdot 0 - 0\cdot 4 = 0$. Under the
$\le 0$ rule the zero triggers a pop, so $M$ is dropped and the edge is the single
segment $\overline{AB}$ — the lean hull with corners only. Under the strict $< 0$
rule the zero does _not_ pop, so $M$ stays and the boundary lists $A, M, B$ — every
point on the fence. The entire difference between "corners" and "on the boundary"
is that one comparison.

## A lower bound: $\Omega(n\log n)$

The $O(n\log n)$ running time is not an artifact of these particular algorithms.
**No** comparison-based hull algorithm can beat it, by the same
[lower-bound argument](/algorithms/sorting/sorting-lower-bounds) that pins
comparison sorting.

> **Theorem.** Computing the convex hull of $n$ points (reported in boundary
> order) requires $\Omega(n\log n)$ time in the algebraic decision-tree model.

> **Proof sketch (reduction from sorting).** Given $n$ reals $x_1, \dots, x_n$ to
> sort, map each to the planar point $(x_i, x_i^2)$. These points lie on the
> parabola $y = x^2$, which is convex, so **every** point is a hull vertex and the
> hull is the entire set. Reading the hull off in boundary order lists the points
> by increasing $x$ — that is, it sorts the $x_i$. A hull algorithm running in
> $o(n\log n)$ would thus sort in $o(n\log n)$, contradicting the
> $\Omega(n\log n)$ comparison-sorting bound established in the
> **sorting-lower-bounds** lesson. $\qed$

$$
% caption: Lifting $x_i\mapsto(x_i,x_i^2)$ puts every point on a convex parabola, so the
%          hull sorts the $x_i$
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.5pt},
  >=stealth, yscale=0.7, scale=1.05]
  \definecolor{acc}{HTML}{2348F2}
  \draw[acc, thick] plot[domain=-2.15:2.15, samples=60] (\x, {\x*\x});
  \foreach \x/\lab in {-2/1,-1/2,0/3,1/4,2/5}
    \node[dot, label={[font=\footnotesize]above left:\lab}] at (\x, {\x*\x}) {};
  \draw[->] (-2.6,-0.55) -- (2.7,-0.55) node[right] {$x$};
  \foreach \x in {-2,-1,0,1,2}
    \draw (\x,-0.45) -- (\x,-0.65);
  \node[font=\footnotesize] at (0,-1.15) {sorted $x_i$};
  \node[acc, font=\footnotesize] at (0,5.05) {hull $=$ all points};
\end{tikzpicture}
$$

So monotone chain and Graham scan are asymptotically optimal: the sort they pay
for is, in a precise sense, _the same sort_ the problem itself requires.

::impl{algo="parabola_sort_reduction"}

## What the hull is good for

The hull is rarely the final answer. It is a preprocessing step that collapses
$n$ messy points down to an ordered convex polygon of $h \le n$ vertices, after
which many "extremal" questions become easy. The key technique is **rotating
calipers**: walk two pointers around the hull in tandem, exploiting the fact that
as one supporting line rotates, the farthest or nearest vertex advances
monotonically.[^skiena-hull] This computes the polygon **diameter** (the
farthest pair of points in the whole set, which must be two hull vertices) in
$O(n)$ time _after_ the hull, rather than the $\Theta(n^2)$ of checking all pairs.

$$
% caption: Rotating calipers: two parallel supporting lines turn around the hull; the
%          diameter is the widest antipodal pair
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.5pt},
  >=stealth, scale=0.95]
  \definecolor{acc}{HTML}{2348F2}
  % a convex hull
  \node[dot] (h0) at (0.3,0.6)  {};
  \node[dot] (h1) at (2.4,0.0)  {};
  \node[dot] (h2) at (4.4,1.0)  {};
  \node[dot] (h3) at (4.6,2.8)  {};
  \node[dot] (h4) at (2.6,3.8)  {};
  \node[dot] (h5) at (0.6,2.6)  {};
  \draw[acc, thick] (h0.center) -- (h1.center) -- (h2.center) -- (h3.center)
    -- (h4.center) -- (h5.center) -- cycle;
  % the antipodal diameter pair (h1 and h4), highlighted
  \node[dot, fill=acc] at (h1) {};
  \node[dot, fill=acc] at (h4) {};
  \draw[acc, very thick] (h1.center) -- (h4.center);
  \node[acc, font=\footnotesize, fill=white, inner sep=1.5pt] at (3.0,2.35) {diameter};
  % two parallel supporting calipers (perpendicular pair of dashed lines)
  \draw[red!75!black, thick, dashed] ($(h1)+(-1.0,-0.5)$) -- ($(h1)+(1.6,0.8)$);
  \draw[red!75!black, thick, dashed] ($(h4)+(-1.6,-0.8)$) -- ($(h4)+(1.0,0.5)$);
  \node[red!75!black, font=\footnotesize] at (3.7,-0.35) {supporting line};
  \node[red!75!black, font=\footnotesize] at (1.3,4.35) {parallel \texttt{caliper}};
\end{tikzpicture}
$$

The same caliper sweep yields the **smallest enclosing rectangle** (its optimal
orientation always has a side flush with a hull edge), the width of the point set,
and the **convex layers** (peel the hull, recurse on the interior). Whenever a
problem cares only about the outermost shape of a point cloud (collision bounds,
fitting, nearest-feature queries), computing the hull first is the standard
first step.[^clrs-hull]

::impl{algo="hull_rotating_calipers"}

## Output-sensitive and higher-dimensional hulls

The standard references give $O(n\log n)$ for the hull, and the parabola lower
bound says that is optimal _when the hull is reported in sorted order_. But that
lower bound applies only because the output
_is_ a sorted sequence of $n$ points. When the hull has just $h \ll n$ vertices,
a lower cost should be possible. Two lines of work address exactly that.

**Chan's algorithm (1996)** resolves this: it computes the hull in
$O(n\log h)$, **output-sensitive** in the true hull size $h$, which matches the
lower bound for every $h$ and beats $O(n\log n)$ whenever the hull is small.[^chan]
The trick combines the two algorithms already in this lesson. Guess a bound $H$ on
$h$; partition the $n$ points into $n/H$ groups of $H$ each and build each group's
hull with Graham scan in $O(H\log H)$, for $O(n\log H)$ total. Then run a gift-wrap
_over the group hulls_, using binary search on each group hull to find its tangent
in $O(\log H)$, so each wrap step costs $O((n/H)\log H)$ and $h$ steps cost
$O(h(n/H)\log H)$. Choosing $H \approx h$ makes both parts $O(n\log h)$. Since $h$
is unknown, Chan runs the whole thing with $H = 2, 4, 16, 256, \dots$ (squaring the
guess) and stops the first time the wrap completes within $H$ steps; the doubling
search adds only a constant factor.

$$
% caption: Chan's algorithm: hull each of the $n/H$ groups (Graham), then gift-wrap over
%          the group hulls with binary-search tangents, for $O(n\log h)$.
\begin{tikzpicture}[>=Stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % three small group hulls
  \foreach \cx/\cy in {0/0, 3/0.4, 1.6/2.4} {
    \begin{scope}[shift={(\cx,\cy)}]
      \draw[black, thick] (0,0) -- (0.9,-0.15) -- (1.1,0.7) -- (0.35,0.95) -- cycle;
    \end{scope}
  }
  \node[black] at (0.55,-0.65) {group hulls (Graham)};
  % the overall gift-wrap outer boundary in accent
  \draw[acc, very thick, dashed]
    (0,0) -- (3.9,0.25) -- (4.1,1.1) -- (2.7,3.35) -- (1.95,3.35) -- (0,0.95) -- cycle;
  \node[acc] at (4.6,2.5) {wrap over hulls};
\end{tikzpicture}
$$

**QuickHull** is the practical divide-and-conquer analogue of quicksort. Take the
two extreme-$x$ points; they split the set into points above and below the line
between them. For the upper part, find the point $f$ farthest from that line — it
is a hull vertex — and recurse on the two sub-lines it forms, discarding every
point inside the triangle. Average performance is $O(n\log n)$ and it is very fast
on typical inputs, but like quicksort it degrades to $\Theta(n^2)$ on adversarial
sets where each split peels off only one point.[^barber] QuickHull is what the
widely used _Qhull_ library implements, and it generalizes cleanly to three and
higher dimensions, where the hull is a polytope with $O(n^{\lfloor d/2\rfloor})$
faces and the plane-sweep intuition of this module no longer applies.

## Takeaways

- The **convex hull** is the smallest convex polygon enclosing a point set (the
  rubber band around the nails), and reporting it in boundary order is the
  foundational problem of planar computational geometry.
- **Andrew's monotone chain** sorts by $(x, y)$, then sweeps a **lower** and
  **upper** hull, **popping** any vertex where the last three points fail to turn
  counterclockwise (cross product $\le 0$). It is $O(n\log n)$, dominated by the
  sort.
- The pop condition is the **orientation primitive** from the previous lesson:
  keep left turns, reject right turns and (by policy) collinear points.
- **Graham scan** achieves the same bound by sorting on **polar angle**; monotone
  chain avoids angle computation and is more numerically stable.
- **Degeneracies**, namely duplicates and collinear hull-edge points, are handled
  by deduplicating and by choosing $<0$ (keep collinear) versus $\le 0$ (drop them).
- Any hull algorithm is $\Omega(n\log n)$ by **reduction from sorting** (lift
  points onto a parabola), so these algorithms are optimal.
- The hull is a **preprocessing** step: **rotating calipers** give the diameter,
  smallest enclosing rectangle, and width in $O(n)$ once the hull is built.

[^clrs-graham]: **CLRS**, Ch. 33 — Computational Geometry (§33.3): Graham's scan sorts by polar angle around the lowest point and maintains a stack of left turns, in $O(n\log n)$.
[^skiena-hull]: **Skiena**, § — Convex Hull: the hull as the most basic geometric structure, with rotating calipers for farthest-pair and enclosing-shape queries.
[^clrs-hull]: **CLRS**, Ch. 33 — Computational Geometry (§33.3): the convex hull as a preprocessing primitive reducing $n$ points to an ordered convex polygon.
[^chan]: Timothy M. Chan, "Optimal output-sensitive convex hull algorithms in two and three dimensions," _Discrete & Computational Geometry_ 16(4), 1996 — the $O(n\log h)$ hull combining group Graham scans with a gift-wrap over group hulls and a doubling search on $H$.
[^barber]: C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa, "The Quickhull Algorithm for Convex Hulls," _ACM Transactions on Mathematical Software_ 22(4), 1996 — the divide-and-conquer QuickHull implemented in the Qhull library, extending to higher dimensions.