vii. Rotating Calipers

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

ll 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]);
    ll 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 in total around the whole loop, so it is $O(n)$, not $O(n^2)$.

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

Proof: the diameter is attained by an antipodal pair, visited monotonically

The diameter is a hull edge’s opposite vertex, or an antipodal pair. For any two points $a,b$ achieving the diameter, both must be hull vertices (any point strictly inside the hull is strictly closer to some hull vertex than a point further out in the same direction — formally, moving a point in the direction away from the segment’s perpendicular bisector strictly increases distance until it hits the hull boundary, so an interior point is never uniquely farthest). Fix hull vertex $a$; the point farthest from $a$ is the vertex $b$ where the supporting line of the hull parallel to the line through $a$ perpendicular to… more directly: $b$ maximizes $|p-a|$ over hull vertices $p$, a function that is unimodal as $p$ walks around the convex hull starting from the vertex nearest $a$ (increases then decreases, since $|p-a{|}^2$ restricted to a convex polygon’s boundary has at most one local max per “side” — a standard fact for distance-to-a-point over a convex curve). Call $(a,b)$ an antipodal pair if the hull has parallel supporting lines through $a$ and through $b$ — equivalently, as the caliper direction rotates through $360°$, both $a$ and $b$ are simultaneously touched by the two parallel calipers for some direction. The diameter pair is always antipodal (if not, a small rotation of the calipers would increase $|a-b|$ further, contradicting maximality — informally, two points not in “opposite supporting line” position have the segment between them not perpendicular to some separating direction, and the rectangle of calipers can be rotated to stretch them apart more).

The sweep visits every antipodal pair, monotonically. As the caliper direction rotates through $360°$ (equivalently, as $i$ advances once fully around the hull), the opposite caliper’s contact vertex $j$ only ever moves forward (never backward) — because the function “edge $i$‘s outward normal direction” is monotonically increasing in angle as $i$ increases, and for each direction there is a unique (or edge-length-tied) extreme vertex $j$ in the opposite direction, also monotonically increasing in angle. This is exactly why while (cross(edge_i, edge_j) > 0) j++ is correct: the cross product test compares the two edges’ directions, advancing $j$ exactly until edge $j$ is no longer “behind” edge $i$ in angular sweep — and since $j$ never needs to move backward, the total advancement of $j$ over the whole outer loop is $O(n)$, not $O(n^2)$. Every antipodal pair is touched at the instant the sweep passes its parallel-supporting-line configuration, so checking $(h[i],h[j])$ and $(h[i+1],h[j])$ at each step of the outer loop (both candidates bracketing the true antipodal moment) catches the true diameter. $■$

Tested against brute-force $O(n^2)$ all-pairs distance on random point sets (hull first), including collinear and duplicate-point degenerate inputs.

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, or [[#Convex Distance
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.

Proof: Toussaint's theorem

Let $R$ be a minimum-area rectangle enclosing convex polygon $C$, with no side of $R$ collinear with an edge of $C$. Then $R$ touches $C$ on each of its four sides at a vertex (not a full edge) of $C$, since no side is edge-aligned. Rotate $R$ slightly (by angle $\theta$) about the touching configuration, keeping it circumscribing $C$ (the four touching vertices slide along $R$‘s sides as it rotates, which is always possible for a small enough $\theta$ since each side touches at an isolated vertex, not a flush edge). The rectangle’s area as a function of the rotation angle $\theta$ is smooth away from edge-alignment events, and a direct computation (the width and height are each of the form $R\cos \theta +S\sin \theta$ for constants $R,S$ depending on the touching vertices, so the area is a sum of such products, differentiable in $\theta$) shows the derivative of the area at $\theta =0$ is generically nonzero unless a side is already edge-aligned — so a small rotation in the direction that decreases area contradicts minimality. (The one case where the derivative vanishes without edge-alignment is a measure-zero configuration that is itself a limit of edge-aligned rectangles, so the infimum is still attained at an edge-aligned configuration.) Hence a minimum must have at least one side flush with an edge. $■$

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 the convex hull trick with monotone queries, D&C DP (monotone argmin), and ordinary 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, since consecutive “edges” with a collinear middle vertex are parallel). Either build the strict hull (keepCollinear=false in 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.

Bounding Rectangle

Smallest-area and smallest-perimeter rectangle (any orientation) enclosing a convex polygon, and whether a $p\times q$ rectangle fits inside an $a\times b$ one.

pair<double, double> minBoundingRectangle(const vector<P>& h) {   // {area, perimeter}
    int n = h.size();
    if (n <= 2) { double len = n == 2 ? dist(h[0], h[1]) : 0; return {0, 2 * len}; }
    double bestArea = 1e18, bestPer = 1e18;
    int right = 0, far = 0, left = 0;
    for (int i = 0; i < n; i++) {
        PD a = toPD(h[i]), b = toPD(h[(i + 1) % n]);
        double len = abs_(b - a);
        PD d = (b - a) * (1.0 / len);                              // unit direction of this edge
        auto along = [&](int k) { return dot(toPD(h[k % n]) - a, d); };
        auto height = [&](int k) { return cross(d, toPD(h[k % n]) - a); };
        if (i == 0) {
            for (int k = 0; k < n; k++) {
                if (along(k) > along(right)) right = k;
                if (height(k) > height(far)) far = k;
                if (along(k) < along(left)) left = k;
            }
        } else {
            const double eps = 1e-9;
            while (along(right + 1) > along(right) + eps) right++;
            while (height(far + 1) > height(far) + eps) far++;
            while (along(left + 1) < along(left) - eps) left++;
        }
        double w = along(right) - along(left), ht = height(far);
        bestArea = min(bestArea, w * ht);
        bestPer = min(bestPer, 2 * (w + ht));
    }
    return {bestArea, bestPer};
}
 
bool rectangleFits(double p, double q, double a, double b) {        // can a p x q rectangle fit in an a x b one?
    if (p < q) swap(p, q);
    if (a < b) swap(a, b);
    if (p <= a && q <= b) return true;                              // axis-aligned fit
    if (q > b) return false;
    double s = p * p + q * q;
    if (s < a * a) return false;
    return b >= (2 * p * q * a + (p * p - q * q) * sqrt(s - a * a)) / s;   // tilted fit, Carver 1956
}

Complexity: $O(n)$ rotating calipers for minBoundingRectangle; $O(1)$ for rectangleFits. An optimal enclosing rectangle has a side on a hull edge (Toussaint), so for every edge, three calipers track: the farthest point along the edge direction, the farthest perpendicular, the farthest against the edge direction.

Proof: the calipers in minBoundingRectangle advance monotonically

Fix edge $i$ with unit direction $d_i$. As $i$ increases by one (moving to the next edge CCW), $d_i$‘s angle increases monotonically (convexity). The extreme vertex in direction $d_i$ (right), in direction $-d_i$ (left), and in the perpendicular direction $d_i^{\perp }$ (far) are each the argmax of a linear functional over the hull’s vertices — and as the functional’s direction rotates monotonically, its argmax vertex index also advances monotonically around the hull (the same unimodal-then-monotone-pointer argument as the diameter proof above, applied to a general direction instead of specifically “away from $a$”). So each of the three pointers only ever needs to move forward across the whole outer loop, giving $O(n)$ total instead of $O(n^2)$.

Proof: rectangleFits (Carver's criterion)

The axis-aligned case is immediate. For the tilted case, place the large rectangle as $[0,a]\times [0,b]$ and the small one rotated by angle $\theta$ with its lower-left corner pinned so two adjacent corners of the small rectangle touch two adjacent sides of the large one (the configuration that lets a rectangle just barely too big to fit axis-aligned slide in at a tilt). Writing the small rectangle’s corners in terms of $p,q,\theta$ and requiring all four to lie within $[0,a]\times [0,b]$ gives, after eliminating $\theta$ (the binding constraint is the fourth corner grazing the far side), the quartic-reducible condition that simplifies to $b\ge \frac{2pqa+(p^2-q^2)\sqrt{p^2+q^2-a^2}}{p^2+q^2}$ whenever $p>a$ — Carver’s 1956 result, obtained by differentiating the fourth corner’s $y$-coordinate as a function of $\theta$ with the touching constraints substituted in, setting the derivative to zero (the extremal tilt), and solving the resulting system. The case split (p<=a && q<=b outright; q>b impossible since even the shorter side overflows; s<a*a impossible since the small rectangle’s diagonal is shorter than $a$, so no tilt reaches corner-to-corner) covers every configuration where the formula’s square root is real and the geometry is as assumed. $■$ (Tested by direct simulation: try the formula’s prediction against a fine sweep over $\theta \in [0,\pi /2]$ checking literal corner-in-rectangle containment.)

Convex Distance

Minimum distance between two convex polygons (0 if they intersect), via the Minkowski difference.

double convexPolygonDistance(vector<P> p, vector<P> q) {  // both CCW, strictly convex
    auto rotateToLowest = [](vector<P>& v) {
        int lo = min_element(v.begin(), v.end(), [](P a, P b) {
                      return a.y != b.y ? a.y < b.y : a.x < b.x;
                  }) - v.begin();
        rotate(v.begin(), v.begin() + lo, v.end());
    };
    vector<P> negQ;
    for (auto& v : q) negQ.push_back(v * (-1));          // -Q of a CCW polygon is still CCW (180 degree rotation)
    rotateToLowest(p);
    rotateToLowest(negQ);                                 // minkowski requires both inputs to start at their lowest point
    vector<P> s = minkowski(p, negQ);                     // from Minkowski Sum
    int k = s.size();
    if (k == 1) return dist(s[0], P{0, 0});
    bool inside = true;
    for (int i = 0; i < k; i++) if (cross(s[i], s[(i + 1) % k]) < 0) inside = false;  // origin on the right of some edge
    if (inside) return 0;
    double best = 1e18;
    for (int i = 0; i < k; i++) best = min(best, distToSegment(P{0, 0}, s[i], s[(i + 1) % k]));
    return best;
}

Complexity: $O(n+m)$. $\mathrm{dist}(P,Q)=$ distance from the origin to $P\oplus (-Q)$ (see Minkowski Sum for why): the Minkowski sum of two convex polygons is convex with at most $n+m$ vertices; the origin inside or on it means the polygons intersect, and otherwise the answer is the distance from the origin to the nearest edge — exactly `distToSegment` minimised over the sum’s edges. For a point and a polygon use $Q=\{\text{point}\}$; for “do two convex polygons intersect”, compare the result with $0$.

Proof: convexPolygonDistance is correct

$\mathrm{cross}(s_i,s_{i+1})\ge 0$ for every edge of a CCW convex polygon $s$ iff the origin is on the left (interior) side of every edge — exactly point-in-convex-polygon’s same-side test specialised to the origin; if it fails for any edge, the origin is outside, and the nearest point of the (convex, hence connected boundary) polygon to the origin lies on the boundary, achieved on whichever edge’s segment is closest — minimised directly by distToSegment over all edges, which is exact (proved in Primitives). The $k=1$ case ($P\oplus (-Q)$ degenerates to a single point, i.e. both $P,Q$ are single points) is immediate. $■$

Tested against a brute-force $O(nm)$ scan (minimum over all pairs of edges, via segment-to-segment distance) on random convex polygon pairs, both disjoint and overlapping.