Pattern Reference
Rotating Calipers
"Width/diameter of convex polygon, minimum bounding rectangle, distance between convex polygons. O(n)."
Loading...
Deep Dive Tutorial
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.
Farthest pair via rotating calipers on convex hull
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);
}Worked Problems
ruler
Rotating calipers applications:
- 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.
- 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.