Pattern Guide
Rotating Calipers & Convex Polygon Queries
"Farthest pair, diameter, closest parallel edges in O(n) after O(n log n) hull."
Rotating calipers is an O(n) technique (after building the convex hull) for: farthest pair of points, diameter of convex polygon, width of convex polygon, closest bichromatic pair, and smallest enclosing rectangle. The idea: two parallel "calipers" rotate around the polygon, and antipodal pairs are visited efficiently. Named for the rotating measurement device.
Problems you can solve with this pattern
3 problems · click any to start solving
function cross(O, A, B) {
return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0]);
}
function dist2(A, B) {
return (A[0]-B[0])**2 + (A[1]-B[1])**2;
}
function convexHull(pts) {
pts.sort((a,b) => a[0]-b[0] || a[1]-b[1]);
const n = pts.length, hull = [];
for (const p of pts) {
while (hull.length >= 2 && cross(hull.at(-2), hull.at(-1), p) <= 0) hull.pop();
hull.push(p);
}
const lower = hull.length + 1;
for (let i = n-1; i >= 0; i--) {
while (hull.length >= lower && cross(hull.at(-2), hull.at(-1), pts[i]) <= 0) hull.pop();
hull.push(pts[i]);
}
return hull.slice(0, -1);
}
// Farthest pair of points (diameter of point set)
function farthestPair(points) {
const hull = convexHull(points);
const n = hull.length;
if (n === 1) return 0;
if (n === 2) return Math.sqrt(dist2(hull[0], hull[1]));
let maxDist = 0;
let j = 1;
for (let i = 0; i < n; i++) {
while (dist2(hull[i], hull[(j+1)%n]) > dist2(hull[i], hull[j])) j = (j+1) % n;
maxDist = Math.max(maxDist, dist2(hull[i], hull[j]), dist2(hull[(i+1)%n], hull[j]));
}
return Math.sqrt(maxDist);
}Rotating calipers: after computing the convex hull, maintain two antipodal points (farthest pair in current caliper direction). As we advance along the hull, we advance the antipodal pointer when the next caliper direction would bring a closer result. For diameter: advance both pointers together, tracking maximum distance. For width: maintain the support line and its antipodal point.
function cross(O, A, B) {
return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0]);
}
function dist2(A, B) {
return (A[0]-B[0])**2 + (A[1]-B[1])**2;
}
function convexHull(pts) {
pts.sort((a,b) => a[0]-b[0] || a[1]-b[1]);
const n = pts.length, hull = [];
for (const p of pts) {
while (hull.length >= 2 && cross(hull.at(-2), hull.at(-1), p) <= 0) hull.pop();
hull.push(p);
}
const lower = hull.length + 1;
for (let i = n-1; i >= 0; i--) {
while (hull.length >= lower && cross(hull.at(-2), hull.at(-1), pts[i]) <= 0) hull.pop();
hull.push(pts[i]);
}
return hull.slice(0, -1);
}
// Farthest pair of points (diameter of point set)
function farthestPair(points) {
const hull = convexHull(points);
const n = hull.length;
if (n === 1) return 0;
if (n === 2) return Math.sqrt(dist2(hull[0], hull[1]));
let maxDist = 0;
let j = 1;
for (let i = 0; i < n; i++) {
while (dist2(hull[i], hull[(j+1)%n]) > dist2(hull[i], hull[j])) j = (j+1) % n;
maxDist = Math.max(maxDist, dist2(hull[i], hull[j]), dist2(hull[(i+1)%n], hull[j]));
}
return Math.sqrt(maxDist);
}- Diameter of convex polygon: O(n)
- Width of convex polygon (minimum distance between parallel support lines): O(n)
- Closest pair on convex polygon: O(n)
- Minimum enclosing rectangle: O(n) (rotate calipers around hull)
Antipodal points: Two hull points are antipodal if there exist parallel supporting lines through them. As we walk around the hull, the antipodal point advances monotonically.
Combined with convex hull: Total complexity O(n log n) for hull + O(n) for rotating calipers = O(n log n) overall.