Rotating Calipers
Walk two pointers around a convex polygon to enumerate antipodal structure without restarting from scratch.
Rotating Calipers
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Rotating calipers is the geometry pattern for convex polygons when one pointer is not enough but restarting the second pointer from scratch would waste too much work. The picture is two supporting lines rotating together, but the contest implementation is usually just a monotone pointer on hull indices.
When to Use It
Use it when:
the input is already a convex polygon or can be reduced to one by taking the convex hull,
the interesting pair or edge moves monotonically around the hull,
you need diameter, width, farthest pair, or another antipodal-style quantity.
Core Idea
For convex polygons, as one edge advances to the next edge in cyclic order, the best opposing point also advances in cyclic order. That monotonicity turns an apparent \(O(n^2)\) pair scan into \(O(n)\) after the hull is known.
Key Insight
The second pointer never needs to move backward. This is the exact geometric analog of a two-pointer proof on arrays: the objective changes smoothly enough that once an index stops being optimal, it will not become optimal again later.
Worked Problem
Problem.
Given \(n\) points in the plane, find the maximum squared distance between any two points.
Why calipers fit.
The farthest pair must be on the convex hull. After building the hull, the diameter can be found by scanning antipodal pairs with one advancing pointer.
Algorithm outline.
Build the convex hull in counterclockwise order.
For each hull edge \((i, i+1)\), advance pointer \(j\) while the area with \(j+1\) increases.
Check the relevant pair distances for \(i\) and \(j\).
Correctness Intuition
Advancing \(j\) while the signed area increases keeps the opposite supporting line as far as possible from edge \((i,i+1)\). Convexity guarantees that once the area starts decreasing, further advancing \(j\) cannot help for the same edge, and the next edge only moves the optimum forward.
Complexity Analysis
After the hull is built in \(O(n \log n)\), the calipers scan is \(O(h)\), where \(h\) is the hull size.
Implementation
The code assumes the convex hull is already built and returns the squared diameter of that hull.
Common Pitfalls
Running calipers on a non-convex polygon.
Forgetting cyclic indexing on the hull.
Mishandling small hull sizes \(h \le 2\).
Comparing floating-point distances when integer squared distance is enough.
Variants / Extensions
Minimum width of a convex polygon.
Maximum area triangle on a convex polygon.
Farthest pair between two convex polygons under specialized setups.
Practice Problems
Diameter of a point set.
Width or thickness of a convex polygon.
Any hull problem where the optimal opposing point moves monotonically.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Point {
long long x;
long long y;
};
long long cross(const Point& a, const Point& b, const Point& c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
long long dist2(const Point& a, const Point& b) {
long long dx = a.x - b.x;
long long dy = a.y - b.y;
return dx * dx + dy * dy;
}
long long convex_polygon_diameter_sq(const vector<Point>& hull) {
int n = (int)hull.size();
if (n <= 1) return 0;
if (n == 2) return dist2(hull[0], hull[1]);
long long answer = 0;
int j = 1;
for (int i = 0; i < n; ++i) {
int ni = (i + 1) % n;
while (true) {
int nj = (j + 1) % n;
if (abs(cross(hull[i], hull[ni], hull[nj])) > abs(cross(hull[i], hull[ni], hull[j]))) {
j = nj;
} else {
break;
}
}
answer = max(answer, dist2(hull[i], hull[j]));
answer = max(answer, dist2(hull[ni], hull[j]));
}
return answer;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.