Rotating Calipers

Role: this file is the conceptual lesson — antipodal-pair theory, the monotonicity argument, and the catalogue of applications (diameter, width, enclosing rectangle, two-hull distance). For a lean paste-ready implementation with the wrap-around / collinear / hull-size edge cases foregrounded, see the companion contest template.

Quick Revisit

• USE WHEN: diameter/farthest pair, minimum width, or other extremal measurements on a convex hull
• INVARIANT: two pointers on the hull advance monotonically; each vertex visited at most twice total
• TIME: O(n) after hull is built | SPACE: O(1) extra
• CLASSIC BUG: missing the second antipodal distance check -- must check both endpoints of the current edge
• PRACTICE: ../12-practice-ladders/08-ladder-mixed.md

The technique for computing diameter, minimum width, and other extremal measurements on convex hulls in $O(n)$ time.

Difficulty: [Advanced]Prerequisites: Convex Hull, Geometry BasicsCF Rating Range: 1700 -- 2100

---

Contents

• 1. Intuition & Concept
• 2. Visual Intuition -- Full Walkthrough
• 3. Applications Beyond Diameter
• 4. C++ STL Reference
• 5. Implementation -- Contest-Ready
• 6. Operations Reference
• 7. Problem Patterns & Tricks
• 8. Contest Cheat Sheet
• 9. Gotchas & Debugging
• 10. Self-Test
• 11. Practice Problems
• 12. Further Reading

Intuition & Concept

Layer 1 -- The Problem

Given $n$ points, find the two points at maximum distance. This is the diameter of the point set.

Brute force: check all $(\genfrac{}{}{0ex}{}{n}{2})$ pairs -- $O(n^2)$.

$n$	$O(n^2)$ pairs	Time at ${10}^8$/s
${10}^3$	$5\times {10}^5$	instant
${10}^5$	$5\times {10}^9$	~50 s
${10}^6$	$5\times {10}^{11}$	~1.4 hours

For $n>{10}^4$ or so, we need something better.

Layer 2 -- Two Key Observations

Observation 1: The farthest pair must both be on the convex hull.

Proof sketch. Suppose the diameter is achieved by points $P$ and $Q$, and $P$ is strictly interior to the hull. Consider the ray from $Q$ through $P$ extended outward; convexity guarantees the ray exits the hull at some boundary point $P^{\prime }$ with $|P^{\prime }Q|>|PQ|$. So $(P,Q)$ was not the maximum — contradiction. Hence both endpoints of any diameter pair are hull vertices, and we only need to consider the $h$ hull vertices (typically $h\ll n$).

Observation 2: As you sweep a direction vector around the hull, the farthest point in that direction moves monotonically around the hull.

This is the key insight that gives us $O(h)$ instead of $O(h^2)$.

Layer 3 -- The Caliper Mental Model

Picture a physical caliper -- two parallel jaws measuring the width of an object. Now place those jaws against two parallel tangent lines of the convex hull:

  ==============================  <-- top caliper jaw (tangent line)
          *---------*
         / E       D \
        /             \
       *F             *C
        \           /
         \       /
          *---*
           A   B
  ==============================  <-- bottom caliper jaw (tangent line)

The distance between the jaws is the "width" in this direction. Now rotate the calipers. At each position, one jaw touches a hull edge and the other touches the farthest vertex.

As the calipers rotate through 180 degrees (a half turn covers all directions because the other half is symmetric), the contact points walk around the hull monotonically. Each vertex is visited at most once by each jaw -- total $O(h)$ steps.

Layer 4 -- Antipodal Pairs

Two hull vertices are antipodal if you can place two parallel lines through them such that the entire hull lies between the lines.

  Antipodal pair (A, D):

     ======= tangent through D ========
              *---------*D
             / E         \
            /             \
           *               *C
            \            /
             \        /
              *----*
           A   B
     ======= tangent through A ========

The diameter is the maximum distance over all antipodal pairs. Rotating calipers enumerate exactly the antipodal pairs.

  Rotating Calipers -- parallel support lines:

       ========== line L1
       |        |
     +-*--------*-+
     |  \      /  |    The calipers are two parallel
     |   +----+   |    lines that rotate together,
     |  /      \  |    always touching the hull at
     +-*--------*-+    antipodal points.
       |        |
       ========== line L2
       ^        ^
      p_i      p_j (antipodal pair)

Layer 5 -- The Algorithm

For finding the diameter:

1. Build the convex hull (Andrew's monotone chain, $O(n\log n)$).
2. Find the starting pair: the topmost vertex (max $y$) and bottommost vertex (min $y$) are antipodal by the horizontal calipers.
3. Rotate: at each step, advance whichever caliper line would rotate by a smaller angle. In practice, this means comparing cross products of successive hull edges to decide which pointer advances.
4. Track the maximum distance across all antipodal pairs visited.

The rotation logic: let edge $e_i=h[i+1]-h[i]$ and edge $e_j=h[j+1]-h[j]$ be the current edges at the two caliper contact points. Advance $j$ if $\text{cross}(e_i,e_j)>0$ (edge $e_j$ "leads" in the rotation), else advance $i$.

  Advance decision -- compare edge angles:

      edge_i        edge_j
    A------>B      C------>D

  cross(edge_i, edge_j) > 0  =>  advance j (j has smaller angle)
  cross(edge_i, edge_j) <= 0 =>  advance i (i has smaller angle)

        j advances          i advances
       +---+               +---+
      / C   \             / C   \
     |   |   |           |   |   |
     | D<+   |           |   +>D |
      \ A   /             \ A   /
       +---+               +---+
        B                    B

What the Code Won't Teach You

The "why are we doing this?" clarity. In contest conditions, the real question is: does this problem reduce to rotating calipers? The signal: a problem on a convex polygon (or one that reduces to a hull computation) where you want to find optimal pairs or measure some property between "opposite" parts of the polygon. If the polygon isn't convex, the approach doesn't apply directly.

The minimum enclosing rectangle variant. This is one of the hardest rotating calipers variants and appears on harder problems. It requires four simultaneous pointers (two pairs of parallel supporting lines forming the rectangle sides). Advancing them correctly -- by minimum rotation angle determined by cross products with multiple hull edges -- is genuinely tricky and requires careful, separate practice.

Rotating calipers is often the second half of a two-part solution. The first part builds the hull; the second part does the calipers sweep. Contestants who run out of time usually implement the hull correctly but fumble the calipers part. Practice them together -- not separately -- to build fluency under time pressure.

---

Visual Intuition -- Full Walkthrough

Diameter of a Hexagonal Hull

Consider a hull with 6 vertices (CCW order):

  A(0,0)  B(4,0)  C(6,3)  D(4,6)  E(1,5)  F(-1,2)

  y
  6 |        D
  5 |  E---/
  4 |  |       \
  3 |  |          C
  2 | F         /
  1 |  \     /
  0 | A---B
    +--+--+--+--+--+--+-> x
   -1  0  1  2  3  4  5  6

Step 1: Find topmost and bottommost.

• Bottom: $A(0,0)$ (index 0) -- min $y$.
• Top: $D(4,6)$ (index 3) -- max $y$.

Starting pointers: $i=0$ (at $A$), $j=3$ (at $D$).

Record ${\text{dist}}^2(A,D)=16+36=52$.

Step 2: Decide which pointer to advance.

Edge from $i$: $e_i=B-A=(4,0)$. Edge from $j$: $e_j=E-D=(-3,-1)$.

$\text{cross}(e_i,e_j)=(4)(-1)-(0)(-3)=-4$.

Cross product $\le 0$, so advance $i$. Now $i=1$ (at $B$), $j=3$ (at $D$).

  Calipers now touching B and D:
  y
  6 |        D  <-- j
  5 |  E---/
  3 |  |          C
  2 | F         /
  0 | A  [B] <-- i
       ^

Record ${\text{dist}}^2(B,D)=0+36=36$. Max so far: 52.

Step 3: $e_i=C-B=(2,3)$, $e_j=E-D=(-3,-1)$.

$\text{cross}(e_i,e_j)=(2)(-1)-(3)(-3)=-2+9=7>0$.

Advance $j$. Now $i=1$ (at $B$), $j=4$ (at $E$).

${\text{dist}}^2(B,E)=9+25=34$. Max: 52.

Step 4: $e_i=C-B=(2,3)$, $e_j=F-E=(-2,-3)$.

$\text{cross}(e_i,e_j)=(2)(-3)-(3)(-2)=-6+6=0$.

Tie -- advance both. $i=2$ (at $C$), $j=5$ (at $F$).

Check both pairs: ${\text{dist}}^2(C,E)=25+4=29$, ${\text{dist}}^2(B,F)=25+4=29$, ${\text{dist}}^2(C,F)=49+1=50$.

Max: 52.

Step 5: $e_i=D-C=(-2,3)$, $e_j=A-F=(1,-2)$.

$\text{cross}(e_i,e_j)=(-2)(-2)-(3)(1)=4-3=1>0$.

Advance $j$. Now $j=0$ (at $A$), $i=2$ (at $C$).

${\text{dist}}^2(C,A)=36+9=45$. Max: 52.

Step 6: $e_i=D-C=(-2,3)$, $e_j=B-A=(4,0)$.

$\text{cross}(e_i,e_j)=(-2)(0)-(3)(4)=-12<0$.

Advance $i$. Now $i=3$ (at $D$), $j=0$ (at $A$).

We've returned to the starting pair $(A,D)$ -- stop.

Result: Maximum squared distance = 52. Diameter = $\sqrt{52}=2\sqrt{13}$. The farthest pair is $(A,D)$.

Summary of the Rotation

  Step  |  i (bottom) |  j (top)  | dist^2 | Action
  ------+-------------+-----------+--------+-------------------
    1   |  A (0)      |  D (3)    |  52    | advance i (cross<0)
    2   |  B (1)      |  D (3)    |  36    | advance j (cross>0)
    3   |  B (1)      |  E (4)    |  34    | advance both (tie)
    4   |  C (2)      |  F (5)    |  50    | advance j (cross>0)
    5   |  C (2)      |  A (0)    |  45    | advance i (cross<0)
    6   |  D (3)      |  A (0)    |  52    | STOP (full rotation)

Six steps for a 6-vertex hull. Always $O(h)$.

  Diameter = max distance between antipodal pairs:

        *---------*  <-- pair 1: dist = 8
       / \       / \
      /   *-----*   \
     /                \
    *                  *  <-- pair 3: dist = 12 (DIAMETER)
     \                /
      \   *-----*   /
       \ /       \ /
        *---------*  <-- pair 2: dist = 9

---

3. Applications Beyond Diameter

Minimum Width

The width of a convex polygon in a given direction is the distance between two parallel supporting lines perpendicular to that direction. The minimum width is the smallest such distance over all directions.

The minimum width always occurs when one supporting line is flush with a hull edge (not a vertex). So for each edge, compute the perpendicular distance to the farthest vertex on the opposite side -- rotating calipers gives you that opposite vertex.

  Minimum width = min perpendicular distance from edge to opposite vertex:

          *--------*
         /  edge e  \
        /             \     <-- perpendicular distance d
       *               *    <-- farthest vertex from edge e
        \            /
         *--------*

Minimum Enclosing Rectangle

A minimum-area enclosing rectangle of a convex polygon must have one side flush with a hull edge. For each edge, use rotating calipers to find:

• The farthest vertex opposite the edge (gives the rectangle height).
• The leftmost and rightmost vertices projected onto the edge (gives width).

This is a 4-caliper variant: one caliper slides along edges, the other three track the extreme vertices in perpendicular and parallel directions.

Merging Two Convex Hulls

Given two disjoint convex hulls, find their common outer tangent lines. Rotating calipers on both hulls simultaneously finds these tangents in $O(h_1+h_2)$.

Bridge Between Two Hulls

Find the edge connecting two separable convex hulls -- the "bridge" that completes the merged hull. This is a subroutine in divide-and-conquer hull algorithms.

---

C++ STL Reference

Function / Type	Header	What it does	Complexity
sort()	<algorithm>	Sort points for hull construction	$O(n\log n)$
max()	<algorithm>	Track maximum distance	$O(1)$
hypot(dx, dy)	<cmath>	$\sqrt{d{x}^2+d{y}^2}$ (final answer)	$O(1)$
vector<P>	<vector>	Hull storage	$O(n)$

---

Implementation -- Contest-Ready

Minimal contest template -- Diameter (squared distance)

Clean diameter implementation

ll diameter2(const vector<P>& h) {
    int n = h.size();
    if (n == 1) return 0;
    if (n == 2) return dist2(h[0], h[1]);

    // j starts at the vertex farthest from the first edge
    int j = 1;
    while (cross(h[1] - h[0], h[(j+1)%n] - h[0]) >
           cross(h[1] - h[0], h[j] - h[0]))
        j = (j + 1) % n;

    ll ans = 0;
    for (int i = 0, jp = j; i <= jp; i++) {
        ans = max(ans, dist2(h[i], h[j]));
        // Advance j while the cross product of edge at i vs edge at j
        // indicates j should rotate further
        while (cross(h[(i+1)%n] - h[i], h[(j+1)%n] - h[j]) > 0) {
            j = (j + 1) % n;
            ans = max(ans, dist2(h[i], h[j]));
        }
    }
    return ans;
}

Explained version

// Returns the SQUARED diameter (maximum squared distance between any two points).
// Input: convex hull in CCW order.
// Time: O(h) where h = hull size.
ll diameter2(const vector<P>& h) {
    int n = h.size();
    if (n == 1) return 0;
    if (n == 2) return dist2(h[0], h[1]);

    // Initialize j to the farthest vertex from edge h[0]->h[1].
    // We compare cross products: cross(edge, h[j]-h[0]) is proportional
    // to the perpendicular distance from h[j] to the line through the edge.
    // Advance j while this distance increases.
    int j = 1;
    while (cross(h[1] - h[0], h[(j+1)%n] - h[0]) >
           cross(h[1] - h[0], h[j] - h[0]))
        j = (j + 1) % n;

    ll ans = 0;
    // For each edge starting at h[i], the antipodal vertex is at or near h[j].
    // As i advances, j only moves forward (monotonicity).
    for (int i = 0, jp = j; i <= jp; i++) {
        ans = max(ans, dist2(h[i], h[j]));

        // Advance j: compare the "angular progress" of edge at i vs edge at j.
        // cross(edge_i, edge_j) > 0 means edge_j lags behind edge_i in the
        // rotation, so j should advance to catch up.
        while (cross(h[(i+1)%n] - h[i], h[(j+1)%n] - h[j]) > 0) {
            j = (j + 1) % n;
            ans = max(ans, dist2(h[i], h[j]));
        }
        // When cross <= 0, edge_i should advance instead (outer loop handles this).
    }
    return ans;
}

Minimum width implementation

// Returns the SQUARED minimum width * (edge_length^2) to stay in integers.
// For actual width, divide by edge length at the end.
// More practically, returns the minimum width as a double.
double min_width(const vector<P>& h) {
    int n = h.size();
    if (n <= 2) return 0.0;

    int j = 1;
    // Find vertex farthest from first edge
    while (cross(h[1] - h[0], h[(j+1)%n] - h[0]) >
           cross(h[1] - h[0], h[j] - h[0]))
        j = (j + 1) % n;

    double ans = 1e18;
    for (int i = 0; i < n; i++) {
        // Advance j to farthest from edge h[i]->h[(i+1)%n]
        P edge = h[(i+1)%n] - h[i];
        while (cross(edge, h[(j+1)%n] - h[i]) > cross(edge, h[j] - h[i]))
            j = (j + 1) % n;

        // Perpendicular distance from h[j] to line through h[i], h[(i+1)%n]
        double d = abs((double)cross(edge, h[j] - h[i])) / hypot(edge.x, edge.y);
        ans = min(ans, d);
    }
    return ans;
}

Full solution -- Farthest Pair

Combines the hull from Convex Hull with diameter2 above. Copy the P, cross, dist2, hull functions from that file, then add:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// ... paste P, cross, dist2, hull from 02-convex-hull.md ...
// ... paste diameter2 from above ...

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> pts(n);
    for (auto& [x, y] : pts) cin >> x >> y;

    auto h = hull(pts);
    int m = h.size();
    if (m == 1) { cout << 0 << "\n"; return 0; }
    if (m == 2) { cout << dist2(h[0], h[1]) << "\n"; return 0; }
    cout << diameter2(h) << "\n";
}

---

Operations Reference

Operation	Time	Space	Notes
Build convex hull	$O(n\log n)$	$O(n)$	Prerequisite
Diameter (farthest pair)	$O(h)$	$O(1)$	Single rotating calipers pass
Minimum width	$O(h)$	$O(1)$	One edge + one vertex per step
Minimum enclosing rectangle	$O(h)$	$O(1)$	Four calipers simultaneously
All antipodal pairs	$O(h)$	$O(h)$	At most $2h$ pairs
Common tangent of two hulls	$O(h_1+h_2)$	$O(1)$	Two-pointer on both hulls

Total pipeline (hull + calipers): $O(n\log n)$ dominated by the sort.

---

Problem Patterns & Tricks

Pattern 1: "Maximum Distance Between Two Points"

Build hull, run rotating calipers for diameter. The answer is always an antipodal pair on the hull.

auto h = hull(pts);
ll d2 = diameter2(h);
cout << fixed << setprecision(6) << sqrt((double)d2) << "\n";
// Or print d2 if squared distance is acceptable

CF Examples: POJ 2187, Kattis Robert Hood

Pattern 2: "Minimum Width / Thickness"

For each hull edge, find the farthest vertex on the opposite side. The minimum perpendicular distance over all edges is the width.

Useful for: fitting shapes through narrow gaps, determining if a polygon fits inside a channel of width $W$.

CF Examples: UVa 10173

Pattern 3: "Minimum Bounding Rectangle"

Extend rotating calipers to four simultaneous extreme-point trackers: one for each side of the rectangle. One side is always flush with a hull edge, so iterate over all edges.

Applications: smallest box to fit a 2D shape, image bounding box.

CF Examples: Kattis Minimum Bounding Rectangle

Pattern 4: "Farthest Point from a Line/Edge"

Given a hull and a query line, find the hull vertex farthest from it. Binary search on the hull or rotating calipers if the lines rotate monotonically.

// Farthest vertex from line through points p, q:
int farthest_from_line(const vector<P>& h, P p, P q) {
    int n = h.size(), best = 0;
    for (int i = 1; i < n; i++)
        if (abs(cross(p, q, h[i])) > abs(cross(p, q, h[best])))
            best = i;
    return best;
}

For single queries, this is $O(h)$. For monotonically rotating queries, use two pointers for $O(1)$ amortized.

Pattern 5: "Merging Two Separated Convex Hulls"

Given two convex hulls where one is entirely to the left of the other, find the upper and lower tangent lines to merge them into one hull. This is a key subroutine in divide-and-conquer hull algorithms.

CF Examples: CF 1017E (Segment Tree + geometry)

Pattern 6: "Maximum Triangle Area"

The maximum-area triangle inscribed in $n$ points has all three vertices on the hull. Use a variant of rotating calipers: fix one vertex, rotate the other two.

// O(h^2) with rotating third vertex:
ll max_triangle_area2(const vector<P>& h) {
    int n = h.size();
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int k = (i + 2) % n;
        for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
            while (abs(cross(h[i], h[j], h[(k+1)%n])) >
                   abs(cross(h[i], h[j], h[k])))
                k = (k + 1) % n;
            ans = max(ans, abs(cross(h[i], h[j], h[k])));
        }
    }
    return ans;  // actual area = ans / 2
}

---

Contest Cheat Sheet

+================================================================+
|                  ROTATING CALIPERS CHEAT SHEET                 |
+================================================================+
| PREREQUISITE: Build convex hull first (O(n log n))             |
+----------------------------------------------------------------+
| DIAMETER (farthest pair):                                      |
|   1. Start j at farthest vertex from first edge                |
|   2. For each edge i, advance j while cross(e_i, e_j) > 0     |
|   3. Record max dist(h[i], h[j]) at each step                 |
|   Time: O(h)                                                   |
+----------------------------------------------------------------+
| MINIMUM WIDTH:                                                 |
|   For each edge, find farthest opposite vertex (same j walk)   |
|   Width = |cross(edge, vertex - edge_start)| / |edge|          |
+----------------------------------------------------------------+
| ADVANCE RULE:                                                  |
|   cross(edge_i, edge_j) > 0  -->  advance j                   |
|   cross(edge_i, edge_j) < 0  -->  advance i                   |
|   cross(edge_i, edge_j) = 0  -->  advance both, check all 4   |
+----------------------------------------------------------------+
| KEY INVARIANT:                                                 |
|   Both pointers only move forward => O(h) total                |
+================================================================+

---

Gotchas & Debugging

Gotcha 1: Modular indexing

Hull is cyclic. Always use (i + 1) % n for the next vertex. Off-by-one in modular arithmetic is the #1 source of bugs.

// Safe next-vertex macro:
auto nxt = [&](int i) { return (i + 1) % n; };

Gotcha 2: Degenerate and collinear hulls

If the hull has 1 or 2 points, calipers don't apply:

if (n == 1) return 0;
if (n == 2) return dist2(h[0], h[1]);

All-collinear inputs give a 2-point hull. Just return dist2(h[0], h[1]).

Gotcha 3: Squared distance vs actual distance

Many problems ask for squared distance to avoid floating point. Don't take sqrt unless the problem explicitly requires it.

Gotcha 4: The j-initialization

The initial position of $j$ matters. For diameter, $j$ should start at the vertex farthest from the first edge (not just $j=1$). The initialization loop handles this:

int j = 1;
while (cross(h[1]-h[0], h[(j+1)%n]-h[0]) > cross(h[1]-h[0], h[j]-h[0]))
    j = (j + 1) % n;

Skipping this can give wrong answers on hulls where the farthest vertex from edge 0 is not vertex 1.

Gotcha 5: The cross = 0 (tie) case

When $\text{cross}(e_i,e_j)=0$, edges are parallel. Check all four combinations: $(h[i],h[j])$, $(h[i],h[j+1])$, $(h[i+1],h[j])$, $(h[i+1],h[j+1])$. Missing this can skip the true maximum.

Gotcha 6: Hull must be in CCW order

Rotating calipers assumes CCW vertex ordering. Andrew's monotone chain gives CCW. If you get a hull from elsewhere, verify the winding direction.

Mental Traps

Trap: "Rotating calipers = rotating a line, so I need trigonometry."

The "rotating" in the name suggests angle-based computation, but the algorithm works entirely with cross products and comparisons -- no sin, cos, or atan2 required. The "rotation" is conceptual: we rotate two parallel supporting lines around the hull. The implementation is a pointer sweep with cross product comparisons.

Trap: "The diameter of a point set can only be between hull vertices."

This is actually true and is the key insight that makes rotating calipers work. But people often state it without being able to prove it. The proof: if neither endpoint of a maximum-distance pair is on the hull, then at least one is in the interior, and you can always find a hull vertex at least as far from the other endpoint. Without internalizing this proof, the algorithm feels like magic.

Trap: "Rotating calipers is just two pointers."

It is two pointers on a convex hull -- but with a specific advancement condition that depends on what quantity you're optimizing. The "two pointers" framing is correct but incomplete. The hard part is deriving the right advancement condition for your specific problem variant (diameter vs. width vs. enclosing rectangle, etc.).

Trap: Thinking there's only one "rotating calipers" algorithm.

Rotating calipers is a family of algorithms. The structure (two pointers, advance by minimum angle, track quantity of interest) is the same, but the specific quantity tracked and the advancement condition differ for diameter, width, minimum enclosing rectangle, maximum inscribed triangle, and more. Each variant has its own subtleties -- don't assume one implementation covers all cases.

Debug checklist

  [ ] Hull is in CCW order?
  [ ] Handled hull size 1 and 2?
  [ ] j initialized correctly (not just j = 1)?
  [ ] Modular arithmetic for all index accesses?
  [ ] Checked the cross = 0 (parallel edges) tie case?
  [ ] Using squared distance to avoid floating point?
  [ ] Total iterations bounded by O(h)?

---

Self-Test

Before moving on, verify you can answer these without opening the reference:

• [ ] Explain why the farthest pair must lie on the convex hull. Give the one-sentence proof (interior points can always be "beaten" by a hull vertex).
• [ ] Write the diameter loop body from memory. Include the pointer advancement condition using cross products and the max-distance update.
• [ ] State what cross(P[i+1]-P[i], P[j+1]-P[j]) > 0 means geometrically. Don't just say "advancement condition" -- explain it in terms of edge angles and which caliper rotates less.
• [ ] Handle the degenerate case: what happens when the hull has only 2 vertices? What do you return, and why don't calipers apply?
• [ ] Name two problem variants beyond diameter (e.g., minimum width, minimum enclosing rectangle) and state the advancement condition for one of them.
• [ ] Explain the cross = 0 tie case. When both edges are parallel, which pairs must you check and why can you miss the true maximum otherwise?
• [ ] Trace the full algorithm by hand on a 5- or 6-vertex hull. Verify that both pointers together take at most $O(h)$ total steps.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Beauty Contest	POJ 2187	Easy	Direct diameter via calipers
2	Robert Hood	Kattis	Easy	Farthest pair, output distance
3	Farthest Pair of Points	SPOJ MFPT	Medium	Standard diameter
4	Minimum Fence	UVa 10173	Medium	Minimum width of hull
5	Smallest Enclosing Box	Kattis	Medium	4-caliper bounding rectangle
6	Cows	POJ 3608	Medium	Min distance between two hulls
7	Max Triangle Area	SPOJ MTRIAREA	Medium	Rotating third vertex
8	Farthest Point Pair	CF 1290A	Medium	Hull + calipers
9	Helicopter Monitoring	CF 1017E	Hard	Merge hulls + tangent lines
10	Rotating Calipers	Gym 104620D	Hard	Multiple caliper applications

---

Further Reading

• cp-algorithms: Rotating Calipers
• Wikipedia: Rotating Calipers
• Shamos, M.I. (1978) -- original rotating calipers paper
• Topcoder: Geometry Concepts (Part 2)
• CF Blog: Geometry Compendium

Cross-references within this notebook:

• Convex Hull -- prerequisite: building the hull
• Geometry Basics -- cross product, point struct
• Half-Plane Intersection -- related convex geometry technique

---

The Aha Moment

Rotating calipers exploits a single key insight: as you walk around a convex hull edge-by-edge, the antipodal point (the farthest point from the current edge) only moves forward, never backward. This monotonicity means you advance two pointers in lockstep -- one traversing edges, one traversing antipodal vertices -- visiting every critical pair in $O(n)$ total, not $O(n^2)$.

Pattern Fingerprint

Fingerprint: "diameter / farthest pair of a convex polygon" -> rotating calipers on convex hull

Fingerprint: "minimum width / thinnest direction of a convex polygon" -> rotating calipers tracking minimum edge-to-antipodal distance

Fingerprint: "merge two convex hulls' extreme measurements" -> rotating calipers on Minkowski sum

Rating Progression

CF Rating	What to Master
1200	Understand that the diameter of a point set = diameter of its convex hull. Brute-force all hull pairs for diameter in $O(h^2)$.
1500	Implement single-antipodal rotating calipers to find the diameter in $O(n)$. Know why the antipodal pointer is monotone.
1800	Use rotating calipers for minimum-width (thinnest strip), maximum distance between two convex polygons, and bridge finding in hull merge.
2100	Co-rotating calipers on two polygons simultaneously (e.g., Minkowski sums, minimum Hausdorff distance). Combine with ternary search for non-convex objectives on hull sequences.

Before You Code Checklist

• [ ] Have I built the convex hull first and verified it is in counter-clockwise order?
• [ ] Is my antipodal advancement using cross-product area comparison (not angle or distance), to stay in integer arithmetic?
• [ ] Does my loop terminate after exactly $n$ edge steps (one full traversal), not fewer or more?
• [ ] Am I advancing the antipodal pointer with a while (not if), since multiple advances can happen per edge?
• [ ] Have I handled the degenerate case where the hull is a single point or a segment (fewer than 3 vertices)?

What Would You Do If...?

Scenario 1: The problem asks for the minimum-width enclosing strip (two parallel lines) of a point set.

Answer: Build the convex hull, then run rotating calipers. For each edge of the hull, compute the distance from that edge's supporting line to the antipodal vertex. Track the minimum over all edges. The minimum width always occurs when one of the strip's lines is flush with a hull edge.

Scenario 2: You need the maximum distance between two disjoint convex polygons.

Answer: The maximum distance between two convex polygons is the maximum distance over all pairs of vertices -- but you don't need $O(n\cdot m)$. Run co-rotating calipers: advance pointers on both hulls simultaneously using cross-product comparisons to find the pair achieving the maximum distance in $O(n+m)$.

Scenario 3: Your rotating calipers gives a slightly wrong diameter -- off by one edge.

Answer: The most common cause: the loop runs for n - 1 edges instead of n. The last edge (from vertex $n-1$ back to vertex $0$) is easily forgotten. Make sure you iterate for (int i = 0; i < n; i++) and index edges as (hull[i], hull[(i+1) % n]).

The Mistake That Teaches

I was solving a "diameter of a point set" problem. Built the hull -- correct. Wrote the rotating calipers -- looked correct. But on one test case with 200,000 points, my answer was slightly smaller than expected.

I added debug output and found the antipodal pointer was stuck. The bug: I was advancing the antipodal point with if instead of while. On most hulls, the antipodal vertex advances by one per edge step, so if works. But when the hull has a long flat edge followed by a sharp spike, the antipodal point needs to jump multiple vertices in a single edge step. My if only advanced it once, missing the true antipodal.

Changing if to while (with the standard cross(edge, next_antipodal) > cross(edge, current_antipodal) guard) fixed it instantly. Lesson: the monotonicity property guarantees the pointer never moves backward, but it says nothing about moving only one step forward. Always use while.

Debug This

Bug 1: This diameter function sometimes underestimates the answer.

long long diameter2(vector<Point>& hull) {
    int n = hull.size();
    if (n == 1) return 0;
    if (n == 2) return dist2(hull[0], hull[1]);
    int j = 1;
    long long best = 0;
    for (int i = 0; i < n; i++) {
        Point e = hull[(i+1)%n] - hull[i];
        if (cross(e, hull[(j+1)%n] - hull[j]) > 0)
            j = (j + 1) % n;
        best = max(best, dist2(hull[i], hull[j]));
    }
    return best;
}

What's the bug?

The antipodal advancement uses if instead of while. When the hull has edges of varying angular span, the antipodal vertex may need to advance multiple steps for a single edge. Change:

while (cross(e, hull[(j+1)%n] - hull[j]) > 0)
    j = (j + 1) % n;

Also, the function only checks dist2(hull[i], hull[j]) but should also check dist2(hull[(i+1)%n], hull[j]) since the diameter can occur between an edge endpoint and the antipodal vertex.

Bug 2: This minimum-width computation returns zero for some non-degenerate hulls.

double minWidth(vector<Point>& hull) {
    int n = hull.size(), j = 1;
    double best = 1e18;
    for (int i = 0; i < n; i++) {
        Point a = hull[i], b = hull[(i+1)%n];
        Point e = b - a;
        while (cross(e, hull[(j+1)%n] - hull[j]) > 0)
            j = (j + 1) % n;
        double dist = abs(cross(e, hull[j] - a)) / sqrt(dot(e, e));
        best = min(best, dist);
    }
    return best;
}

What's the bug?

The cross() function returns a long long, and abs() on a long long may call the int overload of abs on some compilers, truncating the result to 32 bits (or returning a negative value). This can produce zero or garbage. Use llabs(), abs((long long)...), or cast to double before taking the absolute value:

double dist = fabs((double)cross(e, hull[j] - a)) / sqrt((double)dot(e, e));

Bug 3: This rotating calipers loops forever on certain inputs.

long long diameter2(vector<Point>& hull) {
    int n = hull.size(), j = 1;
    long long best = 0;
    for (int i = 0; i < n; i++) {
        Point e = hull[(i+1)%n] - hull[i];
        while (cross(e, hull[(j+1)%n] - hull[j]) >= 0)
            j = (j + 1) % n;
        best = max(best, dist2(hull[i], hull[j]));
    }
    return best;
}

What's the bug?

Using >= 0 (instead of > 0) in the while condition means that when the cross product is exactly zero (collinear edges on the antipodal side), j keeps advancing. If the hull has parallel edges (e.g., a rectangle), j advances indefinitely because each step yields another zero cross product. Fix: use strict > 0, or add a guard && j != i to bound the advancement. The standard approach is to use > 0 and handle the tie (parallel edge) case separately by also checking dist2 for (j+1) % n.

Historical Origin

The rotating calipers technique was introduced by Michael Shamos in his 1978 PhD thesis at Yale, where he used it to compute the diameter and width of convex polygons in linear time. The name comes from the physical tool -- a pair of parallel jaws that rotate around the shape -- and Shamos showed this mechanical intuition translates directly into an efficient two-pointer algorithm.

Mnemonic Anchor

"Two fingers on the hull, spinning in sync. One pauses while the other catches up. Neither ever goes backward." — rotating calipers in one image.

Common Mistakes

• Only checking one antipodal distance. Must check dist(hull[i], hull[j]) and dist(hull[(i+1)%n], hull[j]) to catch farthest pairs that lie at the far end of the current edge.
• Wrong modular indexing. Off-by-one with (j+1) % n is the most common bug. Double-check whether your hull is closed (first vertex repeated) or open.
• Degenerate hulls. A hull with 1 or 2 points needs special handling — the caliper loop assumes at least 3 vertices.
• Floating-point sqrt in the inner loop. Compare squared distances throughout; only take sqrt once on the final answer if Euclidean distance is required.
• Strict > on collinear edges. When cross == 0 (parallel edges, e.g. a rectangle), strict > skips a valid pair. Either use >= and bound advancement to one full revolution, or check both endpoints of every flat antipodal edge.

---

Recap and Cross-Links

Concept	Link
Geometry Basics	01-geometry-basics
Convex Hull	02-convex-hull
Half-Plane Intersection	04-half-plane-intersection
Practice	Ladder - Mixed