---
title: Polygons & Proximity
module: Computational Geometry
moduleNumber: 11
lessonNumber: 4
order: 1104
summary: |
  Four classics that live on top of the orientation primitive and the convex
  hull. **Closest pair** falls to divide-and-conquer in $\Theta(n\log n)$, where a
  packing argument caps the cross-boundary combine at seven neighbours per point.
  **Point-in-polygon** is the ray-casting parity test or the winding-number count
  that also handles self-intersecting boundaries, both with their edge caveats. The **shoelace formula**
  gives signed area as a sum of cross products, and **rotating calipers** walk the
  hull to read off diameter and width in $O(n)$.
topics: [Geometry]
sources:
  - book: CLRS
    ref: "Ch. 33 — Computational Geometry (§33.4 Closest pair)"
  - book: Skiena
    ref: "§ — Computational Geometry"
  - book: Erickson
    ref: "Ch. — (geometry)"
practice:
  - title: 'Convex Polygon'
    slug: convex-polygon
    difficulty: Medium
  - title: 'K Closest Points to Origin'
    slug: k-closest-points-to-origin
    difficulty: Medium
  - title: 'Erect the Fence'
    slug: erect-the-fence
    difficulty: Hard
---

The first three lessons built the planar toolkit: the
[orientation primitive](/algorithms/computational-geometry/geometric-primitives),
the [convex hull](/algorithms/computational-geometry/convex-hull), and the
[plane sweep](/algorithms/computational-geometry/sweep-line). This lesson applies
those tools to four problems every geometry library ships, each fast and exact
by a counting or sign argument: the
**closest pair** of a point set, the **point-in-polygon** test, the **area** of a
polygon, and the **diameter and width** of a convex polygon. Three of them need
nothing beyond the cross product; the fourth turns the hull into a linear
scan by walking two pointers in lock-step.

## Closest pair of points

> **Problem.** Given $n$ points in the plane, find the two whose Euclidean
> distance is smallest.

The brute force compares all $\binom{n}{2}$ pairs in $\Theta(n^2)$. The classic
improvement is divide-and-conquer, and it is the geometry that makes it work: a
packing bound caps the cross-boundary work at a _constant_ per point. This is the
full treatment — the [Selection lesson](/algorithms/divide-and-conquer/selection)
introduces it as a divide-and-conquer classic alongside sorting, and the
[sweep-line lesson](/algorithms/computational-geometry/sweep-line) gives a
one-pass alternative on a dynamic strip.

**Divide.** Sort by $x$ and split at the median $x$ into a left half $L$ and a
right half $R$ by a vertical line $x = m$. **Conquer.** Recurse on each half;
let $\delta_L$ and $\delta_R$ be the best distances found, and
$\delta = \min(\delta_L, \delta_R)$. **Combine.** The closest pair overall is
either one of these two _or_ a pair that **straddles** the line — one point in
$L$, one in $R$ — at distance $< \delta$. The whole difficulty is bounding that
straddling case.

$$
% caption: Divide at the median $x = m$ into left half $L$ and right half $R$; recurse
%          on each, then check pairs straddling the line
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.5pt},
  >=stealth, x=10mm, y=10mm]
  \definecolor{acc}{HTML}{2348F2}
  % left half region tint
  \fill[acc!10] (-2.6,-0.3) rectangle (0,3.3);
  % right half region tint (a distinguishable lighter blue)
  \fill[acc!20] (0,-0.3) rectangle (2.6,3.3);
  % dividing line
  \draw[dashed, thick] (0,-0.5) -- (0,3.6);
  \node[font=\footnotesize] at (0,3.85) {dividing line: x = m};
  % left points
  \fill[acc] (-2.1,0.6) circle (1.6pt);
  \fill[acc] (-1.4,2.4) circle (1.6pt);
  \fill[acc] (-0.7,1.3) circle (1.6pt);
  \fill[acc] (-1.9,1.9) circle (1.6pt);
  \node[font=\footnotesize, acc] at (-1.7,-0.6) {left half $L$};
  % right points
  \fill[acc!60!black] (0.6,1.9) circle (1.6pt);
  \fill[acc!60!black] (1.4,0.8) circle (1.6pt);
  \fill[acc!60!black] (2.1,2.5) circle (1.6pt);
  \fill[acc!60!black] (1.0,2.9) circle (1.6pt);
  \node[font=\footnotesize, acc!60!black] at (1.4,-0.6) {\texttt{right} half $R$};
\end{tikzpicture}
$$

A straddling pair closer than $\delta$ must have both endpoints within horizontal
distance $\delta$ of the line, so both lie in a vertical **strip** of width
$2\delta$ centred on $x = m$. Discard everything outside the strip; sort the
survivors by $y$ (in practice, filter the already-$y$-sorted list); then walk up
the strip. The decisive fact is that each point need only be compared against a
_constant_ number of its successors in $y$-order.

> **Lemma (Strip packing).** Sort the strip points by $y$. For any strip point
> $p$, every later point that could lie within $\delta$ of $p$ sits among the next
> **seven** points in the $y$-order.

> **Proof.** A point $q$ above $p$ with $\dist(p, q) < \delta$ has
> $p_y \le q_y < p_y + \delta$, so $q$ lies in the $2\delta \times \delta$
> rectangle spanning the strip just above $p$. Tile that rectangle with a grid of
> cells of side $\delta/2$; it holds exactly $2 \times 4 = 8$ cells. No cell can
> contain two strip points: two points in one cell lie on the **same side** of the
> dividing line (each cell sits entirely left or entirely right of $x = m$), so by
> the recursive guarantee they are $\ge \delta$ apart — yet two points in a
> $\delta/2$ square are at most $\frac{\delta}{2}\sqrt2 < \delta$ apart, a
> contradiction. Hence the rectangle holds at most $8$ points, one of them $p$
> itself, leaving at most $7$ candidates, all later than $p$ in $y$-order. $\qed$

$$
% caption: Strip of width $2\delta$; the box above $p$ tiles into 8 cells of side
%          $\delta/2$, so at most 7 later points can beat $\delta$
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.5pt},
  >=stealth, x=10mm, y=10mm]
  \definecolor{acc}{HTML}{2348F2}
  % dividing line and strip
  \fill[acc!12] (-1,-0.5) rectangle (1,4.6);
  \draw[dashed] (0,-0.5) -- (0,4.6);
  \node[font=\footnotesize] at (0,4.95) {dividing line};
  \draw[gray] (-1,-0.5) -- (-1,4.6);
  \draw[gray] (1,-0.5) -- (1,4.6);
  \draw[<->] (-1,-0.85) -- (1,-0.85);
  \node[font=\footnotesize] at (0,-1.2) {strip width};
  % the point p
  \fill[acc] (-0.4,0.8) circle (1.8pt);
  \node[font=\footnotesize, anchor=east] at (-1.5,0.4) {$p$};
  \draw[->, thin] (-1.45,0.45) -- (-0.45,0.75);
  % box above p: 2 wide x 1 tall (2 delta x delta), 8 cells of side delta/2
  \draw[acc, very thick] (-1,0.8) rectangle (1,1.8);
  \foreach \gx in {-0.5,0,0.5} { \draw[acc!45] (\gx,0.8) -- (\gx,1.8); }
  \draw[acc!45] (-1,1.3) -- (1,1.3);
  \node[font=\footnotesize, acc, anchor=west] at (1.7,1.3) {8 cells};
  \draw[->, acc] (1.6,1.3) -- (1.05,1.3);
  % a far point, too high to matter
  \fill[red!75!black] (0.45,3.6) circle (1.8pt);
  \node[font=\footnotesize, red!75!black, anchor=west] at (1.7,3.6) {beyond reach};
  \draw[->, thin, red!75!black] (1.6,3.6) -- (0.6,3.6);
\end{tikzpicture}
$$

$$
% caption: Strip points in $y$-order; from $p$ only the next 7 successors can lie within
%          $\delta$, so each point makes a constant number of checks
\begin{tikzpicture}[
  every node/.style={font=\small},
  >=stealth, x=11mm, y=8mm]
  \definecolor{acc}{HTML}{2348F2}
  % a vertical y-ordered column of strip points
  \foreach \i/\yy in {0/0,1/0.85,2/1.55,3/2.3,4/2.95,5/3.7,6/4.4,7/5.1,8/5.85,9/6.6} {
    \fill[acc!25] (0,\yy) circle (1.7pt);
  }
  % p is the current point near the bottom
  \fill[acc] (0,0) circle (2.2pt);
  \node[font=\footnotesize, acc, anchor=east] at (-0.35,0) {$p$};
  % window covering the next 7 successors
  \draw[acc, very thick] (-0.55,0.5) rectangle (0.55,5.45);
  \node[font=\footnotesize, acc, anchor=west] at (0.75,3.0) {next 7 in $y$-order};
  \draw[->, acc] (0.7,3.0) -- (0.6,3.0);
  % a successor beyond the window: out of reach
  \fill[red!75!black] (0,6.6) circle (2.0pt);
  \node[font=\footnotesize, red!75!black, anchor=west] at (0.35,6.6) {beyond reach};
  % the upward scan direction
  \draw[->, acc!60] (-0.95,0) -- (-0.95,5.3);
  \node[font=\footnotesize, acc!60!black, anchor=east, rotate=90] at (-1.05,2.6) {scan upward};
\end{tikzpicture}
$$

The combine step therefore makes $O(1)$ distance checks per strip point, for
$O(n)$ work. The recurrence is the familiar one,

$$
T(n) \;=\; 2\,T(n/2) \;+\; \Theta(n),
$$

which the [Master Theorem](/algorithms/foundations/recurrences) solves in its
balanced case ($a = b^{\,d}$ with $a = 2,\, b = 2,\, d = 1$), giving
$T(n) = \Theta(n\log n)$. The one implementation subtlety is the inner sort: a
naive $y$-sort of the strip each level would add a $\log n$ factor. Sorting once
by $y$ up front and filtering that order at each level keeps the combine linear,
so the bound holds.[^clrs-closest]

```algorithm
caption: $\textsc{Closest-Pair}(P_x, P_y)$ — $P_x$ sorted by $x$, $P_y$ by $y$
number: 1
$n \gets |P_x|$
if $n \le 3$ then
  return brute-force closest pair      // base case, $O(1)$
$m \gets (P_x[\lfloor n/2\rfloor])_x$  // median $x$ as the dividing line
split $P_x$ into left $L_x$, right $R_x$ at index $\lfloor n/2\rfloor$
partition $P_y$ into $L_y, R_y$ by side of $m$  // keeps each half $y$-sorted
$(a, b) \gets \textsc{Closest-Pair}(L_x, L_y)$
$(c, d) \gets \textsc{Closest-Pair}(R_x, R_y)$
$\delta \gets \min(\dist(a,b),\ \dist(c,d))$
$S \gets [\,q \in P_y : |q_x - m| < \delta\,]$  // strip, still $y$-sorted
for each $q$ in $S$, in $y$-order do
  for each of the next $7$ points $r$ after $q$ in $S$ do
    if $\dist(q, r) < \delta$ then update best pair and $\delta$
return the closest of the left, right, and strip pairs
```

The distance comparisons can stay exact: comparing $\dist(p,q)$
against $\delta$ is comparing **squared** distances $(p_x-q_x)^2 + (p_y-q_y)^2$
against $\delta^2$, which are integers for integer inputs — no square root, no
rounding, the same discipline as the orientation primitive.

::impl{algo="geometry,closest_pair_planar"}

## Point in polygon

Given a simple polygon $P$ (vertices $V_0, \dots, V_{n-1}$ in order) and a query
point $q$, is $q$ inside, outside, or on the boundary? Two tests dominate; both
were named in the [primitives lesson](/algorithms/computational-geometry/geometric-primitives),
and we make them precise here, boundary caveats included.

### Ray casting (the parity test)

Shoot a ray from $q$ in a fixed direction — conventionally along $+x$ — and count
how many polygon edges it crosses. The **Jordan curve theorem** guarantees that a
ray from an interior point crosses the boundary an **odd** number of times, and a
ray from an exterior point an **even** number. So an odd crossing count means
_inside_.

$$
% caption: A $+x$ ray from $q$ crosses an odd count (inside); from $r$ an even count
%          (outside)
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.4pt},
  >=stealth, scale=0.9]
  \definecolor{acc}{HTML}{2348F2}
  \draw[thick] (0,0) -- (5,0) -- (5,4) -- (2.6,2.1) -- (0,4) -- cycle;
  % interior query point low in the solid part: +x ray crosses only the right wall = 1
  \node[dot, fill=acc, label={[fill=white, inner sep=1pt]above left:$q$}] (q) at (0.7,1.3) {};
  \draw[acc, very thick, ->] (q) -- (6.1,1.3);
  \fill[acc] (5,1.3) circle (1.5pt);
  \node[acc, font=\footnotesize, anchor=west] at (6.2,1.3) {odd (1) means inside};
  % exterior query point sitting IN the notch (above the dip, outside the polygon):
  % its +x ray crosses the right notch wall then the right outer wall = 2 = even
  \node[dot] (q2) at (2.55,3.0) {};
  \node[font=\small] at (2.2,3.35) {$r$};
  \draw[dashed, ->] (q2) -- (6.1,3.0);
  \fill (3.74,3.0) circle (1.5pt);
  \fill (5,3.0) circle (1.5pt);
  \node[font=\footnotesize, anchor=west] at (6.2,3.0) {even (2) means outside};
\end{tikzpicture}
$$

The arithmetic per edge $\overline{V_i V_{i+1}}$ is a two-line test: the edge can
cross the horizontal ray at $y = q_y$ only if one endpoint is strictly above
$q_y$ and the other not above it, and then the crossing $x$ must lie to the right
of $q_x$. Both conditions reduce to sign comparisons; the second avoids dividing
by cross-multiplying.

The pitfalls are all **degenerate** rays — those grazing a vertex or running along
an edge — and they are what make naive implementations report nonsense.

> **Note (Tie-breaking).** Treat each edge as **half-open** in $y$: count the edge
> only when exactly one endpoint is **strictly above** $q_y$ (so
> $(V_i)_y > q_y \ne (V_{i+1})_y \le q_y$ or vice versa). This counts a vertex
> shared by two edges exactly once when the ray passes through it, and ignores
> horizontal edges (both endpoints at the same height fail the strict test) — the
> two cases that otherwise double-count or miscount.

> **Remark (Boundary).** Parity classifies _interior_ versus _exterior_ but says
> nothing reliable about $q$ **on** an edge — there a crossing is ambiguous. If the
> boundary must count as "inside" (or be reported separately), test it first:
> $q$ is on edge $\overline{V_i V_{i+1}}$ iff $\ccw(V_i, V_{i+1}, q)
> = 0$ and $q$ lies within the edge's bounding box. Run that on-segment check over
> all edges before the parity count.

::impl{algo="point_in_polygon#point_in_polygon"}

### Winding number

The parity test is blind to how the boundary _wraps_ around $q$, which is why it
breaks on self-intersecting polygons. The **winding number** $w(q)$ counts the net
number of full turns the boundary makes around $q$ as it is traversed once. For a
simple polygon $w(q) = \pm 1$ inside (sign by orientation) and $0$ outside; for a
self-intersecting polygon the magnitude can exceed $1$, and the **nonzero rule**
($q$ inside iff $w(q) \ne 0$) is the one graphics systems use.

Computed naively this would sum signed _angles_ — irrational, floating point. The
exact version sums **signed edge crossings** of the $+x$ ray instead, weighting by
direction: an edge crossing the ray **upward** contributes $+1$, **downward**
$-1$. The sum is $w(q)$, computed entirely from orientation signs.

> **Claim.** For a simple polygon, the winding number agrees with parity: $q$ is
> inside iff $w(q) \ne 0$ iff the unsigned crossing count is odd. Winding strictly
> generalizes parity, staying correct when the boundary self-overlaps, at the same
> $O(n)$ cost.

$$
% caption: Winding by signed ray crossings: the $+x$ ray from $q$ meets one upward edge
%          $(+1)$ and one downward edge $(-1)$; for this simple polygon $w(q)=1-0$, inside.
\begin{tikzpicture}[
  every node/.style={font=\footnotesize},
  dot/.style={circle, fill, inner sep=1.4pt},
  >=stealth, scale=0.9]
  \definecolor{acc}{HTML}{2348F2}
  % a simple pentagon, q inside; the +x ray leaves through two edges
  \draw[thick] (0,0) -- (5,0.6) -- (4.4,3.4) -- (2.2,2.2) -- (0.6,3.6) -- cycle;
  \node[dot, fill=acc, label={[label distance=1pt]below:$q$}] (q) at (1.6,1.4) {};
  \draw[acc, very thick, ->] (q) -- (6.0,1.4);
  % the two crossings: right wall (going up as traversed CCW -> +1), notch wall
  \fill[acc] (4.83,1.4) circle (1.5pt);
  \node[acc, anchor=west] at (4.5,1.9) {up: +1};
  % the polygon here crosses the ray only once to the right -> w=1
  \node[anchor=west] at (6.1,1.4) {net $w = 1$: inside};
\end{tikzpicture}
$$

Both tests are $O(n)$ per query. When the polygon is **convex** and many queries
are expected, the [primitives lesson](/algorithms/computational-geometry/geometric-primitives)'s
$O(\log n)$ fan binary search wins after an $O(n)$ preprocess.

::impl{algo="point_in_polygon#point_in_polygon_winding"}

## Polygon area: the shoelace formula

The [primitives lesson](/algorithms/computational-geometry/geometric-primitives)
introduced the **shoelace formula** for the area of a simple polygon with vertices
$V_0, \dots, V_{n-1}$ in order (indices mod $n$):

$$
\Area(P) \;=\; \frac12\abs{\sum_{i=0}^{n-1} \parens{x_i\, y_{i+1} - x_{i+1}\, y_i}}
\;=\; \frac12\abs{\sum_{i=0}^{n-1} V_i \times V_{i+1}}.
$$

Here we prove it. The cleanest argument is the **trapezoid sum**: each edge, with
the $x$-axis, bounds a trapezoid whose signed area is added as the boundary is
walked, and the trapezoids below exterior edges cancel against those below
interior edges, leaving exactly the enclosed region.

> **Theorem (Shoelace).** For a simple polygon with vertices listed
> counterclockwise, $\sum_{i} (x_i y_{i+1} - x_{i+1} y_i) = 2\Area(P)$;
> clockwise listing negates it.

> **Proof.** The directed edge from $V_i = (x_i, y_i)$ to $V_{i+1} =
> (x_{i+1}, y_{i+1})$, together with the verticals dropped to the $x$-axis, bounds
> a trapezoid of signed area
> $$\tfrac12 (x_i - x_{i+1})(y_i + y_{i+1}),$$
> the average height $\tfrac12(y_i + y_{i+1})$ times the signed width
> $(x_i - x_{i+1})$. The sign is positive when the edge runs **right to left**
> (top of the polygon) and negative left to right (bottom), so summing over the
> boundary adds the area under the top chain and subtracts the area under the
> bottom chain — exactly the enclosed area. Expanding and summing,
> $$\sum_i \tfrac12 (x_i - x_{i+1})(y_i + y_{i+1}) = \tfrac12 \sum_i (x_i y_{i+1} - x_{i+1} y_i),$$
> after the $x_i y_i$ and $x_{i+1} y_{i+1}$ terms cancel telescopically around the
> closed loop. This is the shoelace sum, equal to $2\Area(P)$. $\qed$

$$
% caption: Each edge with the $x$-axis bounds a signed trapezoid; top edges add area,
%          bottom edges subtract, leaving the polygon
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.5pt},
  >=stealth, scale=0.95]
  \definecolor{acc}{HTML}{2348F2}
  % polygon vertices (triangle for clarity)
  \coordinate (A) at (1,1.2);
  \coordinate (B) at (5,0.6);
  \coordinate (C) at (3.4,3.2);
  % axis
  \draw[->] (-0.2,0) -- (6.2,0) node[right] {$x$};
  % trapezoid under the top edge C->A (right to left): positive, blue
  \fill[acc!20] (3.4,0) -- (3.4,3.2) -- (1,1.2) -- (1,0) -- cycle;
  % trapezoid under the top edge B->C: positive, green
  \fill[green!28] (5,0) -- (5,0.6) -- (3.4,3.2) -- (3.4,0) -- cycle;
  % trapezoid under the bottom edge A->B (left to right): negative, red
  \fill[red!22] (1,0) -- (1,1.2) -- (5,0.6) -- (5,0) -- cycle;
  % polygon outline on top
  \draw[acc, very thick] (A) -- (B) -- (C) -- cycle;
  \draw[dashed] (A) -- (1,0);
  \draw[dashed] (B) -- (5,0);
  \draw[dashed] (C) -- (3.4,0);
  \node[dot] at (A) {}; \node[anchor=east] at (A) {$V_0$};
  \node[dot] at (B) {}; \node[anchor=west] at (B) {$V_1$};
  \node[dot] at (C) {}; \node[anchor=south] at (C) {$V_2$};
  \node[acc, font=\footnotesize] at (1.9,1.7) {add};
  \node[green!55!black, font=\footnotesize] at (4.25,1.4) {add};
  \node[red!75!black, font=\footnotesize] at (2.6,0.3) {subtract};
\end{tikzpicture}
$$

The sum is an integer for integer vertices, so the area is an exact
half-integer.[^skiena-area] Dropping the absolute value keeps the sign, which
gives the **winding direction** for free: positive means the vertices are
counterclockwise, negative clockwise — the cheapest orientation test for a whole
polygon.

::impl{algo="shoelace"}

## Rotating calipers: diameter and width

The [convex hull lesson](/algorithms/computational-geometry/convex-hull) closed by
promising that the hull turns many extremal queries into linear scans. The
technique is **rotating calipers**, and the cleanest instance is the
**diameter** — the greatest distance between any two points of a set.

> **Lemma (Diameter on the hull).** The two farthest points of a set are both
> **hull vertices**, and they form an **antipodal** pair: there exist parallel
> supporting lines of the hull, one through each.

> **Proof.** If $p$ is not a hull vertex it lies in the hull's interior or on an
> edge, so for any $q$ some hull vertex is at least as far from $q$ as $p$ is;
> hence a farthest pair can be taken on the hull. The supporting line through $p$
> perpendicular to $\overline{pq}$ leaves all points on $p$'s side (else a point
> beyond it would be farther from $q$), and symmetrically at $q$ — two parallel
> supporting lines, so the pair is antipodal. $\qed$

Checking all $\binom{h}{2}$ hull-vertex pairs is $\Theta(h^2)$. Rotating calipers
do it in $O(h)$ by exploiting **monotonicity**: imagine two parallel lines
("calipers") squeezing the hull, and rotate them together through $180°$. As the
calipers turn, each touches a hull vertex; the contact points advance **around the
hull in step**, never backtracking, because the support direction is monotone.
Every antipodal pair is realized as some caliper orientation, so walking the two
contact pointers once around the hull visits all candidate pairs.

Concretely, for hull vertices in counterclockwise order, the area of the triangle
$V_i V_{i+1} V_j$ (a cross product) is maximized, over $j$, at the vertex
**farthest** from edge $\overline{V_i V_{i+1}}$. As $i$ advances by one edge, the
farthest vertex $j$ only moves **forward**, so a single linear walk of $j$ keeps
pace with $i$. Each antipodal pair encountered is a diameter candidate.

$$
% caption: Two parallel calipers rotate around the hull; antipodal contact pairs include
%          the diameter (widest) and width (narrowest gap)
\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] (h0) at (0.3,0.7) {};
  \node[dot] (h1) at (2.5,0.0) {};
  \node[dot] (h2) at (4.5,1.1) {};
  \node[dot] (h3) at (4.6,2.9) {};
  \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;
  % diameter pair h1 and h4 (widest)
  \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 (1.45,1.9) {diameter};
  % two parallel calipers touching the antipodal pair
  \draw[acc!55!black, thick, dashed] ($(h1)+(-1.1,-0.45)$) -- ($(h1)+(1.5,0.6)$);
  \draw[acc!55!black, thick, dashed] ($(h4)+(-1.5,-0.6)$) -- ($(h4)+(1.1,0.45)$);
  \node[acc!55!black, font=\footnotesize] at (4.1,-0.35) {\texttt{caliper}};
  \node[acc!55!black, font=\footnotesize] at (1.2,4.35) {parallel \texttt{caliper}};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Diameter}(H)$ — farthest pair via rotating calipers, $H$ a CCW hull
number: 2
$h \gets |H|$
if $h \le 2$ then
  return the only pair
$j \gets 1;\ best \gets 0$           // $j$ = current farthest vertex
for $i \gets 0$ to $h - 1$ do
  // advance $j$ while the next vertex is farther from edge $\overline{V_i V_{i+1}}$
  while $\area(H_i, H_{i+1}, H_{j+1}) > \area(H_i, H_{i+1}, H_j)$ do
    $j \gets (j + 1) \bmod h$
  $best \gets \max(best,\ \dist(H_i, H_j),\ \dist(H_{i+1}, H_j))$
return $best$
```

$$
% caption: As edge index $i$ advances by one, the antipodal pointer $j$ only steps
%          forward; the two contact pointers make a single monotone trip around the hull
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.4pt},
  >=stealth, scale=0.85]
  \definecolor{acc}{HTML}{2348F2}
  % a small hull, shown twice for two consecutive steps
  \foreach \k/\dx in {0/0, 1/6.4} {
    \begin{scope}[shift={(\dx,0)}]
      \coordinate (p0) at (0.4,0.6);
      \coordinate (p1) at (2.4,0.1);
      \coordinate (p2) at (3.7,1.7);
      \coordinate (p3) at (2.6,3.3);
      \coordinate (p4) at (0.6,2.7);
      \draw[acc, thick] (p0)--(p1)--(p2)--(p3)--(p4)--cycle;
      \foreach \p in {p0,p1,p2,p3,p4} \fill[acc!30] (\p) circle (1.6pt);
    \end{scope}
  }
  % step 1: edge p0-p1 (bottom), farthest vertex p3
  \draw[acc, very thick] (0.4,0.6) -- (2.4,0.1);
  \fill[acc] (0.4,0.6) circle (2pt);
  \fill[acc] (2.4,0.1) circle (2pt);
  \fill[green!55!black] (2.6,3.3) circle (2.2pt);
  \draw[acc!55, dashed] (1.4,0.35) -- (2.6,3.3);
  \node[font=\footnotesize, acc] at (1.4,-0.5) {edge $i$};
  \node[font=\footnotesize, green!45!black] at (2.6,3.7) {farthest $j$};
  % step 2: edge advances to p1-p2, j stays at p3 (forward only)
  \begin{scope}[shift={(6.4,0)}]
    \draw[acc, very thick] (2.4,0.1) -- (3.7,1.7);
    \fill[acc] (2.4,0.1) circle (2pt);
    \fill[acc] (3.7,1.7) circle (2pt);
    \fill[green!55!black] (2.6,3.3) circle (2.2pt);
    \draw[acc!55, dashed] (3.05,0.9) -- (2.6,3.3);
    \node[font=\footnotesize, acc] at (3.4,-0.5) {edge $i$ add 1};
    \node[font=\footnotesize, green!45!black] at (2.6,3.7) {$j$ steps \texttt{forward}};
  \end{scope}
\end{tikzpicture}
$$

Because $j$ only ever advances and wraps once, the inner `while` does $O(h)$ total
work across all $i$ — the pointer makes a single trip around the hull. The
diameter scan is therefore $O(h)$, and $O(n\log n)$ end-to-end once the hull is
built, against $\Theta(n^2)$ for all-pairs.[^skiena-calipers] The `area` calls are
cross products, so distances enter only at the final `max` (and even there,
comparing **squared** distances keeps it exact).

The same caliper sweep answers the dual question, the **width** — the smallest
distance between two parallel supporting lines, i.e. the narrowest slab containing
the polygon. The minimum-width slab always has one line **flush with a hull edge**,
so rotate one caliper along each edge in turn and track the antipodal vertex's
perpendicular distance (a cross product divided by the edge length); the minimum
over edges is the width. It drives smallest-enclosing-rectangle and
collision-clearance queries, again in $O(h)$ after the hull.

::impl{algo="rotating_calipers"}

## Voronoi, Delaunay, and spatial trees

Closest-pair answers one proximity question for one query. Real systems ask it
repeatedly — nearest hospital, nearest cell tower, nearest neighbor for a
classifier — and want a **structure**, built once, that answers each query fast.
The two canonical structures are duals of each other.

The **Voronoi diagram** of $n$ sites partitions the plane into one cell per site,
the cell of site $s$ being every point closer to $s$ than to any other site. Its
edges are the perpendicular bisectors between neighboring sites, and a nearest-site
query becomes point location in this diagram. The **Delaunay triangulation** is
its dual: connect two sites whenever their Voronoi cells share an edge. Delaunay
triangulations have a defining property — the circumcircle of every triangle is
**empty** of other sites — that makes them maximize the minimum angle, so they
avoid the sliver triangles that wreck interpolation and mesh quality.[^delaunay]
Both are built in $O(n\log n)$, by Fortune's sweep from the
[previous lesson](/algorithms/computational-geometry/sweep-line) or by randomized
incremental insertion, and either one yields the closest pair as a by-product: the
two nearest sites are always joined by a Delaunay edge.

$$
% caption: Voronoi cells (one per site, nearest-point regions) and the dual Delaunay
%          triangulation joining sites with adjacent cells.
\begin{tikzpicture}[>=Stealth, font=\footnotesize,
    s/.style={circle, fill, inner sep=1.5pt}]
  \definecolor{acc}{HTML}{2348F2}
  % sites
  \node[s] (a) at (0.4,0.6) {};
  \node[s] (b) at (3.0,0.2) {};
  \node[s] (c) at (4.0,2.4) {};
  \node[s] (d) at (1.4,3.0) {};
  \node[s] (e) at (2.2,1.6) {};
  % Delaunay edges (accent)
  \draw[acc, thick] (a)--(b) (b)--(c) (c)--(d) (d)--(a) (a)--(e) (b)--(e) (c)--(e) (d)--(e);
  \node[acc, anchor=west] at (4.3,2.4) {Delaunay};
  % a few Voronoi bisector segments (muted grey), schematic
  \draw[black, dashed] (1.7,0.4) -- (1.5,1.5) -- (0.9,2.9);
  \draw[black, dashed] (1.5,1.5) -- (3.1,1.5);
  \draw[black, dashed] (3.1,1.5) -- (3.5,0.2);
  \draw[black, dashed] (3.1,1.5) -- (3.9,2.0);
  \node[black, anchor=west] at (4.3,1.0) {Voronoi};
\end{tikzpicture}
$$

When the data is high-dimensional or the queries are approximate, Voronoi diagrams
become impractical (their size grows as $O(n^{\lceil d/2\rceil})$), and the tool of
choice is a **spatial tree**. A **k-d tree** recursively splits the points by
alternating coordinate axes, giving $O(\log n)$ expected nearest-neighbor queries
in low dimensions; **R-trees** group nearby objects into bounding rectangles for
disk-resident spatial databases; and for the high-dimensional nearest-neighbor
search behind modern embeddings, exact methods lose to **locality-sensitive
hashing** and graph-based approximate indexes such as HNSW.[^ann] All of these
structures rest on the same primitive this module started with: every one
decides "which side" and "closer to which" with orientation and
distance comparisons, and keeps them exact where correctness of the combinatorics
depends on it.

## Takeaways

- **Closest pair** is divide-and-conquer: split at the median $x$, recurse, then
  scan a width-$2\delta$ **strip**. The **strip-packing lemma** caps the combine at
  $7$ comparisons per point, giving $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)$
  by the [Master Theorem](/algorithms/foundations/recurrences). Compare squared
  distances to stay exact.
- **Point-in-polygon** by **ray casting**: an odd count of $+x$-ray crossings means
  inside (Jordan curve), with half-open-edge tie-breaking for vertex/horizontal
  grazes and a separate on-segment test for the boundary.
- The **winding number** sums signed crossings ($+1$ up, $-1$ down); $w(q) \ne 0$
  means inside and stays correct for self-intersecting polygons, where parity fails.
- The **shoelace formula** $\frac12\abs{\sum_i V_i \times V_{i+1}}$ is proved
  by the **trapezoid sum**: top edges add, bottom edges subtract, telescoping to
  the enclosed area; its sign gives the winding direction.
- **Rotating calipers** read the **diameter** (farthest pair, an antipodal hull
  pair) and the **width** (narrowest slab, flush with a hull edge) in $O(h)$ by
  advancing one monotone pointer around the hull — $O(n\log n)$ after the hull
  versus $\Theta(n^2)$ brute force.

[^clrs-closest]: **CLRS**, Ch. 33 — Computational Geometry (§33.4): divide-and-conquer closest pair, the $\delta$-strip, and the constant-neighbour packing bound that makes the combine linear.
[^skiena-area]: **Skiena**, § — Computational Geometry: the shoelace (surveyor's) formula as a signed sum of cross products, whose sign encodes vertex orientation.
[^skiena-calipers]: **Skiena**, § — Computational Geometry: rotating calipers on the convex hull for the diameter (farthest pair) and width, in linear time after the hull.
[^delaunay]: The Voronoi/Delaunay duality and the empty-circumcircle (max-min-angle) property are treated in Mark de Berg et al., _Computational Geometry: Algorithms and Applications_ (3rd ed.), Chs. 7 and 9; both structures build in $O(n\log n)$ via Fortune's sweep or randomized incremental insertion.
[^ann]: Piotr Indyk and Rajeev Motwani, "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality," _STOC_ 1998 (locality-sensitive hashing); Yu. A. Malkov and D. A. Yashunin, "Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs," _IEEE TPAMI_ 42(4), 2020 (HNSW).