Rotating Calipers

Sweep a pair of parallel lines around a convex hull, keeping them tangent to it. Because both contact points move monotonically, a full rotation costs $O(n)$ total — a two-pointer walk around the hull.

Diameter (farthest pair) — the canonical use

long long hullDiameter2(const vector<P>& h) {         // squared, exact
    int n = h.size();
    if (n == 1) return 0;
    if (n == 2) return norm2(h[1] - h[0]);
    long long best = 0;
    for (int i = 0, j = 1; i < n; i++) {
        // advance j while the area of the triangle grows
        while (cross(h[(i+1)%n] - h[i], h[(j+1)%n] - h[j]) > 0) j = (j + 1) % n;
        best = max({best, norm2(h[j] - h[i]), norm2(h[(i+1)%n] - h[j])});
    }
    return best;
}

The cross(...) > 0 test asks “does rotating the caliper to the next edge of $i$ still leave $j$ behind?” — the two-pointer invariant. Each pointer advances at most $n$ times, so the whole loop is $O(n)$.

The diameter of a point set is the diameter of its hull, so the full algorithm is $O(n\log n)$ (hull) $+O(n)$.

What calipers compute

Quantity	Method
Diameter (farthest pair)	as above
Width (minimum-width strip)	minimise the distance from each edge to the farthest vertex
Minimum-area enclosing rectangle	one side lies on a hull edge (Toussaint); track the four extreme points
Minimum-perimeter enclosing rectangle	same sweep, different objective
Maximum-area inscribed triangle	two nested pointers, $O(n^2)$
Distance between two convex polygons	walk both simultaneously
Closest pair of two convex polygons	same
Common tangents of two hulls	same
Merging two hulls	find the upper and lower tangents
All antipodal pairs	the calipers enumerate exactly these, $O(n)$ of them

Minimum enclosing rectangle

Toussaint’s theorem: the minimum-area rectangle enclosing a convex polygon has one side collinear with a polygon edge.

So iterate over the $n$ edges, and for each maintain (by rotating calipers) the extreme vertex in the perpendicular direction and in both parallel directions. $O(n)$ total.

The general principle

Whenever a quantity depends on two points of a convex object and the optimum’s second point moves monotonically as the first one does, a two-pointer walk works. Recognising that monotonicity is the whole insight — the “rotating calipers” name just describes the picture.

The same monotonicity underlies:

• CHT with monotone queries,
• D&C DP (monotone argmin),
• two-pointer techniques on sorted arrays.

Antipodal pairs

A pair of hull vertices is antipodal if there exist parallel supporting lines through both. A convex polygon with $n$ vertices has $O(n)$ antipodal pairs, and the calipers enumerate all of them — which is why the diameter is $O(n)$ rather than $O(n^2)$.

Degenerate cases

Collinear points on the hull

If your hull retains collinear boundary points, the cross(...) > 0 test can stall (the cross product is 0 forever). Either build the strict hull (using <= 0 in the monotone chain), or change the test to >= 0 with a step counter to guarantee termination.

Also handle $n=1$ and $n=2$ separately, as in the code above.

When it does not apply

Calipers need convexity. For a non-convex polygon the farthest pair is still on the hull (so take the hull first), but “width”, “minimum enclosing rectangle” and distance queries about the polygon itself are different problems.

See also: Convex Hull · Minkowski Sum · Closest Pair