Rotating Calipers
Introduction
Rotating calipers is a technique for scanning pairs of supporting lines of a convex polygon. It is used after computing the convex hull of the given point set.
Let
\[ H=(\b{p}_0,\b{p}_1,\ldots,\b{p}_{m-1}) \]
be the vertices of a convex polygon in counterclockwise order. For an edge
\[ \b{e}_i=\b{p}_{i+1}-\b{p}_i, \]
where indices are taken modulo $m$, a point $\b{p}_j$ is antipodal to the edge if it maximizes the signed area
\[ \left[ \b{e}_i \times (\b{p}_j-\b{p}_i) \right]_z. \]
Geometrically, this means that the line through $\b{p}_j$ parallel to the edge is a supporting line farthest from the edge. Rotating calipers tracks this antipodal index while the edge direction rotates along the polygon.
Explanation
For each edge $i$, define
\[ A_i(j)=\left[ (\b{p}_{i+1}-\b{p}_i)\times(\b{p}_j-\b{p}_i) \right]_z. \]
Since $H$ is convex and counterclockwise, $A_i(j)$ is unimodal as $j$ moves cyclically around the polygon. Therefore the antipodal index for edge $i$ can be found by moving $j$ forward while
\[ A_i(j+1)>A_i(j). \]
When the edge changes from $i$ to $i+1$, the antipodal index never needs to move backward. Thus all antipodal pairs can be scanned with two pointers.
For the diameter problem, we use the fact that a farthest pair of vertices is an antipodal pair. During the scan, whenever $j$ is antipodal to edge $(\b{p}_i,\b{p}_{i+1})$, we check the distances from $\b{p}_j$ to $\b{p}_i$ and $\b{p}_{i+1}$. The maximum of these values is the squared diameter.
The visualizer below shows the edge, the antipodal vertex, and the best segment found so far.
Proof of Correctness
First, we prove that the pointer movement finds the antipodal vertex for each edge.
Proof. Fix an edge $i$. The value $A_i(j)$ is twice the signed area of the triangle
\[ (\b{p}_i,\b{p}_{i+1},\b{p}_j). \]
Equivalently, it is the edge length multiplied by the perpendicular distance from $\b{p}_j$ to the line through the edge. As $j$ moves around a convex polygon, this distance increases until the farthest supporting line is reached, and then decreases. Thus $A_i(j)$ is unimodal. The while loop
\[ A_i(j+1)>A_i(j) \]
stops exactly when $j$ is a maximizer of $A_i$.
When $i$ increases by one, the direction of the supporting edge rotates counterclockwise. For a convex polygon, the farthest parallel supporting line also rotates counterclockwise. Hence its contact vertex cannot move backward in cyclic order. Therefore the single pointer $j$ finds the antipodal vertex for every edge while advancing only forward.
Now we prove that the diameter is found.
Proof. Let $(\b{a},\b{b})$ be a pair of vertices with maximum Euclidean distance. Consider two lines perpendicular to $\overline{\b{a}\b{b}}$, one through $\b{a}$ and one through $\b{b}$. If any point of the polygon lay outside this strip, its distance to one of $\b{a}$ or $\b{b}$ would be larger, contradicting maximality. Thus these two lines are parallel supporting lines of the polygon. So $\b{a}$ and $\b{b}$ form an antipodal pair.
The rotating calipers scan enumerates all antipodal pairs generated by polygon edges. For each such pair, it checks the relevant endpoint distances. Since every diameter pair is antipodal, the maximum distance checked by the algorithm is exactly the diameter.
Complexity
Let $m$ be the number of vertices of the convex hull. The edge index $i$ makes one full traversal of the polygon. The antipodal index $j$ also advances at most one full traversal. Therefore the rotating calipers scan takes
\[ O(m) \]
time and $O(1)$ additional memory.
If the convex hull must be computed from $N$ input points first, the total complexity is
\[ O(N\log N). \]
Code
The following code computes the squared diameter of a convex polygon. The input hull must be in counterclockwise order and must not repeat the first vertex at the end.
using ll = long long;
struct Point {
ll x, y;
Point operator-(const Point& other) const {
return {x - other.x, y - other.y};
}
};
__int128 cross(Point a, Point b) {
return (__int128)a.x * b.y - (__int128)a.y * b.x;
}
__int128 dist2(Point a, Point b) {
__int128 dx = (__int128)a.x - b.x;
__int128 dy = (__int128)a.y - b.y;
return dx * dx + dy * dy;
}
__int128 diameter2(const vector<Point>& hull) {
int n = (int)hull.size();
if(n <= 1) return 0;
if(n == 2) return dist2(hull[0], hull[1]);
auto area = [&](int i, int j) {
int ni = (i + 1) % n;
return cross(hull[ni] - hull[i], hull[j] - hull[i]);
};
int j = 1;
__int128 ans = 0;
for(int i=0; i<n; i++) {
int ni = (i + 1) % n;
while(area(i, (j + 1) % n) > area(i, j)) {
j = (j + 1) % n;
}
ans = max(ans, dist2(hull[i], hull[j]));
ans = max(ans, dist2(hull[ni], hull[j]));
}
return ans;
}
If an actual pair of points is required, store the pair whenever ans is updated.
If the input is an arbitrary point set, compute its convex hull first and run the function on the hull.
Applications
- Diameter of a convex polygon
- Diameter of a finite point set after convex hull
- Minimum width of a convex polygon
- Minimum-area enclosing rectangle
- Maximum distance between two convex polygons
- Separating-axis style geometric optimization
