Rotating Calipers (Diameter of a Convex Polygon)
Rotating Calipers sweeps antipodal pairs around a convex polygon in linear O(n) time to find the farthest pair of points (diameter), polygon width, and minimum-area enclosing rectangle.
Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code
Rotating Calipers (Diameter of a Convex Polygon)
Rotating Calipers is the geometric equivalent of Two Pointers around a convex polygon! Imagine placing two parallel lines touching opposite sides of a convex hull and rotating them $360^\circ$. Because the farthest vertex j from edge (i, i + 1) moves monotonically around the hull as i advances, all antipodal pairs are visited in $O(n)$ time—finding the diameter (farthest pair of points) of $n$ 2D points in $O(n \log n)$ total time!
At a Glance
| Property | Value |
| :--- | :---: |
| Hull Construction | $O(n \log n)$ via Convex Hull |
| Calipers Sweep | $O(n)$ (pointer j wraps at most once) |
| Best Used When | Farthest pair of points, polygon width, minimum bounding rectangle |
---
Practice Problems
Hard
1. Farthest Pair of Points in 2D (Squared Diameter)
Given $n$ 2D points, find the maximum squared Euclidean distance between any two points in $O(n \log n)$ time.
Approach: Compute the CCW Convex Hull h (size m). For each edge h[i] -> h[(i + 1) % m], advance j while the triangle area abs(cross(h[i], h[ni], h[nj])) increases, updating best = max(best, distSq(h[i], h[j]), distSq(h[ni], h[j])). Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
struct Pt {
long long x, y;
bool operator<(const Pt& o) const { return x != o.x ? x < o.x : y < o.y; }
bool operator==(const Pt& o) const { return x == o.x && y == o.y; }
};
long long cross(const Pt& O, const Pt& A, const Pt& B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
long long distSq(const Pt& a, const Pt& b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
long long maxDistSq(std::vector<Pt> pts) {
std::sort(pts.begin(), pts.end());
pts.erase(std::unique(pts.begin(), pts.end()), pts.end());
int n = static_cast<int>(pts.size());
if (n <= 1) return 0;
if (n == 2) return distSq(pts[0], pts[1]);
std::vector<Pt> h;
for (const auto& p : pts) {
while (h.size() >= 2 && cross(h[h.size() - 2], h.back(), p) <= 0) h.pop_back();
h.push_back(p);
}
size_t low = h.size();
for (int i = n - 2; i >= 0; --i) {
while (h.size() > low && cross(h[h.size() - 2], h.back(), pts[i]) <= 0) h.pop_back();
h.push_back(pts[i]);
}
h.pop_back();
int m = static_cast<int>(h.size());
long long best = 0;
for (int i = 0, j = 1; i < m; ++i) {
int ni = (i + 1) % m;
while (std::abs(cross(h[i], h[ni], h[(j + 1) % m])) > std::abs(cross(h[i], h[ni], h[j]))) {
j = (j + 1) % m;
}
best = std::max({best, distSq(h[i], h[j]), distSq(h[ni], h[j])});
}
return best;
}
int main() {
std::cout << maxDistSq({{0, 0}, {3, 0}, {3, 4}, {0, 4}, {1, 2}}) << "\n"; // 3^2 + 4^2 = 25
return 0;
}
</details>
---
Related Algorithms
- Convex Hull — prerequisite step before Rotating Calipers.
- Two Pointers — linear 1D counterpart.