Convex Hull

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

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

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.

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)$.

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 $\mathrm{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 $\mathrm{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.

from typing import Iterable

from hull_geometry import Point, cross, squared_distance

def jarvis_march(points: Iterable[Point]) -> list[Point]:
  """
    Convex hull of `points`, in counterclockwise boundary order, keeping\n
    only true corners. Fewer than three distinct points are returned\n
    sorted, as-is.\n
  """
  unique: list[Point] = sorted(set(points))
  if len(unique) < 3:
    return unique

  # leftmost, then lowest — a guaranteed hull vertex.
  start: Point = min(unique)
  hull: list[Point] = []
  current: Point = start

  while True:
    hull.append(current)

    # seed with any point other than the current one.
    candidate: Point = unique[0] if unique[0] != current else unique[1]

    # pick the most clockwise contender, ties broken by distance, so the
    # boundary wraps counterclockwise.
    for contender in unique:
      if contender == current:
        continue
      orientation: int = cross(current, candidate, contender)
      if orientation < 0 or (
        orientation == 0
        and squared_distance(current, contender)
        > squared_distance(current, candidate)
      ):
        candidate = contender

    # stop once the wrap returns to the start.
    current = candidate
    if current == start:
      break

  return hull

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.

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.

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$.

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.

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.

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 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.

from typing import Iterable

from hull_geometry import Point, cross

def monotone_chain(points: Iterable[Point], keep_collinear: bool = False) -> list[Point]:
  """
    Convex hull of `points`, returned in counterclockwise boundary order.\n
    With `keep_collinear` False the hull holds only true corners; True keeps\n
    every point lying on a hull edge. For fewer than three distinct points\n
    the deduplicated, sorted points are returned as-is.\n
  """
  ordered: list[Point] = sorted(set(points))
  if len(ordered) < 3:
    return ordered

  def turns_inward(below: Point, pivot: Point, candidate: Point) -> bool:
    """
      Whether `pivot` should pop: the triple does not turn left.\n
      When collinear points are kept, only a strict right turn pops.\n
    """
    orientation: int = cross(below, pivot, candidate)
    return orientation < 0 if keep_collinear else orientation <= 0

  def build_chain(sweep: list[Point]) -> list[Point]:
    """
      One monotone sweep: push each point, popping the top while the last\n
      three points fail to turn counterclockwise.\n
    """
    chain: list[Point] = []
    for candidate in sweep:
      while len(chain) >= 2 and turns_inward(chain[-2], chain[-1], candidate):
        chain.pop()
      chain.append(candidate)
    return chain

  lower: list[Point] = build_chain(ordered)
  upper: list[Point] = build_chain(list(reversed(ordered)))

  # the last point of each chain is the first of the other (global min/max),
  # so drop one copy of each shared endpoint before concatenating.
  return lower[:-1] + upper[:-1]

from typing import NamedTuple

class Point(NamedTuple):
  """
    A planar point with integer x and y components.\n
    Integer coordinates keep the cross product exact, so orientation never\n
    misfires from floating-point rounding.\n
  """
  x: int
  y: int

def cross(origin: Point, first: Point, second: Point) -> int:
  """
    Orientation of the ordered triple origin -> first -> second.\n
    Returns (first - origin) x (second - origin): > 0 left turn,\n
    < 0 right turn, 0 collinear.\n
  """
  return (
    (first.x - origin.x) * (second.y - origin.y)
    - (first.y - origin.y) * (second.x - origin.x)
  )

def squared_distance(first: Point, second: Point) -> int:
  """
    Squared Euclidean distance between two points.\n
    Squared so the comparison stays exact integer arithmetic — taking the\n
    root is never needed to decide which of two pairs is farther apart.\n
  """
  delta_x: int = first.x - second.x
  delta_y: int = first.y - second.y
  return delta_x * delta_x + delta_y * delta_y

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)$.¹

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 $atan2$ (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.

from functools import cmp_to_key
from typing import Iterable

from hull_geometry import Point, cross, squared_distance

def graham_scan(points: Iterable[Point], keep_collinear: bool = False) -> list[Point]:
  """
    Convex hull of `points`, in counterclockwise boundary order.\n
    With `keep_collinear` False only true corners are kept; True keeps every\n
    point lying on a hull edge. Fewer than three distinct points are\n
    returned sorted, as-is.\n
  """
  unique: list[Point] = sorted(set(points))
  if len(unique) < 3:
    return unique

  # lowest y, then lowest x — guaranteed to be a hull vertex.
  pivot: Point = min(unique, key=lambda point: (point.y, point.x))
  rest: list[Point] = [point for point in unique if point != pivot]

  def by_angle(first: Point, second: Point) -> int:
    """
      Order two points by polar angle around the pivot; nearer first when\n
      the angle ties, so collinear runs are radially sorted.\n
    """
    # a left turn means `first` comes earlier in angular order.
    orientation: int = cross(pivot, first, second)
    if orientation > 0:
      return -1
    if orientation < 0:
      return 1

    # collinear: the nearer point sorts first.
    near: int = squared_distance(pivot, first)
    far: int = squared_distance(pivot, second)
    return -1 if near < far else (1 if near > far else 0)

  rest.sort(key=cmp_to_key(by_angle))

  # to keep collinear points on the final edge (pivot back to the last
  # corner), the trailing collinear run must be reversed so it reads outward.
  if keep_collinear:
    tail: int = len(rest) - 1
    while tail > 0 and cross(pivot, rest[tail], rest[tail - 1]) == 0:
      tail -= 1
    rest[tail:] = reversed(rest[tail:])

  def turns_inward(below: Point, pivot_point: Point, candidate: Point) -> bool:
    """
      Whether `pivot_point` should pop: the triple does not turn left.\n
    """
    orientation: int = cross(below, pivot_point, candidate)
    return orientation < 0 if keep_collinear else orientation <= 0

  # scan in angular order, popping any vertex that fails to turn left.
  hull: list[Point] = [pivot]
  for candidate in rest:
    while len(hull) >= 2 and turns_inward(hull[-2], hull[-1], candidate):
      hull.pop()
    hull.append(candidate)

  return hull

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, $\mathrm{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 that pins comparison sorting.

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.

from typing import Iterable

from hull_geometry import Point
from monotone_chain import monotone_chain

def lift_to_parabola(values: Iterable[int]) -> list[Point]:
  """
    Map each real x to the lifted point (x, x^2) on the parabola y = x^2.\n
  """
  return [Point(value, value * value) for value in values]

def sort_via_hull(values: Iterable[int]) -> list[int]:
  """
    Sort `values` ascending by computing the convex hull of their parabola\n
    lifts and reading the x-coordinates in boundary order. Duplicates\n
    collapse onto the same point, so the result holds each distinct value\n
    once — the reduction's whole point is that the hull *is* the sorted set.\n
  """
  lifted: list[Point] = lift_to_parabola(values)
  hull: list[Point] = monotone_chain(lifted)

  # the hull comes back counterclockwise starting at the lowest-x vertex; on
  # a strictly convex parabola that order is exactly increasing x.
  return sorted(point.x for point in hull)

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.² 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.

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.³

from typing import Iterable, NamedTuple, Optional

from hull_geometry import Point, cross, squared_distance
from monotone_chain import monotone_chain

def _signed_polygon_area_doubled(hull: list[Point]) -> int:
  """
    Twice the signed area of a polygon by the shoelace formula.\n
    Positive when the vertices wind counterclockwise.\n
  """
  # sum the shoelace cross terms over each consecutive edge.
  total: int = 0
  count: int = len(hull)
  for index in range(count):
    current: Point = hull[index]
    following: Point = hull[(index + 1) % count]
    total += current.x * following.y - following.x * current.y

  return total

class Diameter(NamedTuple):
  """
    The farthest pair of points and their squared separation.\n
  """
  first: Point
  second: Point
  squared_length: int

def hull_diameter(points: Iterable[Point]) -> Optional[Diameter]:
  """
    The farthest pair of points in the set, found by rotating calipers in\n
    O(n) after the hull (O(n log n) overall). Returns None for an empty set\n
    and a degenerate self-pair for a single distinct point.\n
  """
  hull: list[Point] = monotone_chain(points)
  if not hull:
    return None

  # degenerate hulls: a single point pairs with itself, two points pair.
  if len(hull) == 1:
    only: Point = hull[0]
    return Diameter(only, only, 0)
  if len(hull) == 2:
    return Diameter(hull[0], hull[1], squared_distance(hull[0], hull[1]))

  # seed the best with the first edge, then rotate calipers around the hull.
  count: int = len(hull)
  best: Diameter = Diameter(hull[0], hull[1], squared_distance(hull[0], hull[1]))
  antipodal: int = 1

  for index in range(count):
    following: int = (index + 1) % count

    # advance the far pointer while the next vertex is farther from the
    # current edge — the area test compares perpendicular distances.
    while abs(
      cross(hull[index], hull[following], hull[(antipodal + 1) % count])
    ) > abs(cross(hull[index], hull[following], hull[antipodal])):
      antipodal = (antipodal + 1) % count

    # both endpoints of the edge can pair with the antipodal vertex.
    for endpoint in (index, following):
      separation: int = squared_distance(hull[endpoint], hull[antipodal])
      if separation > best.squared_length:
        best = Diameter(hull[endpoint], hull[antipodal], separation)
  return best

class BoundingRectangle(NamedTuple):
  """
    A minimum-area enclosing rectangle: its four corners (counterclockwise)\n
    and its area.\n
  """
  corners: tuple[Point, Point, Point, Point]
  area: float

def _dot(vector: Point, point: Point) -> int:
  """
    Dot product of a direction vector with a point's position vector.\n
  """
  return vector.x * point.x + vector.y * point.y

def _cross_scalar(vector: Point, point: Point) -> int:
  """
    Scalar cross of a direction vector with a point — its signed extent\n
    along the perpendicular direction.\n
  """
  return vector.x * point.y - vector.y * point.x

def minimum_bounding_rectangle(points: Iterable[Point]) -> Optional[BoundingRectangle]:
  """
    The smallest-area rectangle enclosing all points, by trying every hull\n
    edge as a candidate orientation (rotating calipers). Returns None for an\n
    empty set. Degenerate (collinear) inputs yield a zero-area rectangle.\n
  """
  hull: list[Point] = monotone_chain(points)
  if not hull:
    return None
  if len(hull) < 3:
    # all points collinear (or fewer than three): a zero-area "rectangle".
    span: int = len(hull)
    corners: tuple[Point, Point, Point, Point] = (
      hull[0 % span],
      hull[1 % span],
      hull[2 % span],
      hull[3 % span],
    )
    return BoundingRectangle(corners, 0.0)

  # ensure counterclockwise so the edge normal points outward consistently.
  if _signed_polygon_area_doubled(hull) < 0:
    hull.reverse()

  count: int = len(hull)
  best: Optional[BoundingRectangle] = None
  for index in range(count):
    # take each hull edge as a candidate rectangle orientation.
    edge_start: Point = hull[index]
    edge_end: Point = hull[(index + 1) % count]
    direction: Point = Point(edge_end.x - edge_start.x, edge_end.y - edge_start.y)

    # skip a zero-length (duplicate-vertex) edge.
    length_squared: float = float(_dot(direction, direction))
    if length_squared == 0.0:
      continue

    # project every hull vertex onto the edge direction and its normal; the
    # rectangle spans the extreme projections in each axis.
    along_values: list[int] = [_dot(direction, vertex) for vertex in hull]
    across_values: list[int] = [_cross_scalar(direction, vertex) for vertex in hull]
    min_along, max_along = min(along_values), max(along_values)
    min_across, max_across = min(across_values), max(across_values)

    # the rectangle's side lengths are the projection spans, normalized.
    width: float = (max_along - min_along) / (length_squared ** 0.5)
    height: float = (max_across - min_across) / (length_squared ** 0.5)
    area: float = width * height
    if best is None or area < best.area:
      # unit vectors along the edge and its outward normal.
      length: float = length_squared ** 0.5
      unit_along: tuple[float, float] = (direction.x / length, direction.y / length)
      unit_across: tuple[float, float] = (-unit_along[1], unit_along[0])

      def corner(along: int, across: int) -> Point:
        position_x: float = (
          unit_along[0] * along / length + unit_across[0] * across / length
        )
        position_y: float = (
          unit_along[1] * along / length + unit_across[1] * across / length
        )
        return Point(round(position_x), round(position_y))

      # the four corners are the extreme projections, counterclockwise.
      corners = (
        corner(min_along, min_across),
        corner(max_along, min_across),
        corner(max_along, max_across),
        corner(min_along, max_across),
      )
      best = BoundingRectangle(corners, area)

  return best

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.⁴ 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.

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.⁵ 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.