Rotating Calipers — Diameter, Width, and Closest Pair on Convex Hulls
- Rotating calipers: O(n) scan of antipodal vertex pairs after O(n log n) convex hull. Reduces many O(n²) problems to O(n).
- Each vertex is antipodal to O(1) others as we rotate 360° — the total antipodal pairs is O(n).
- Applications: diameter, minimum width, minimum bounding rectangle, closest pair between hulls.
Rotating calipers, introduced by Michael Shamos in 1978, is an O(n) technique for computing geometric properties of convex polygons that would naively require O(n²) comparisons. The key insight: many geometric properties depend only on antipodal vertex pairs — pairs of vertices with parallel supporting lines. As you rotate 360°, each vertex becomes antipodal to at most 2 other vertices, so the total number of antipodal pairs is O(n).
Polygon Diameter — Farthest Pair of Points
The diameter of a convex polygon is the maximum distance between any two vertices. Naively O(n²) — but with rotating calipers, O(n) after the hull is built.
from math import dist def polygon_diameter(hull: list[tuple]) -> float: """Maximum distance between any two hull vertices. O(n).""" n = len(hull) if n == 1: return 0 if n == 2: return dist(hull[0], hull[1]) def cross_len(o, a, b): return abs((a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])) max_dist = 0 j = 1 for i in range(n): # Advance j while cross product increases (antipodal tracking) while cross_len(hull[i], hull[(i+1)%n], hull[(j+1)%n]) > \ cross_len(hull[i], hull[(i+1)%n], hull[j]): j = (j + 1) % n max_dist = max(max_dist, dist(hull[i], hull[j]), dist(hull[(i+1)%n], hull[j])) return max_dist hull = [(0,0),(3,0),(3,4),(0,4)] # 3x4 rectangle — diameter = 5 print(f'Diameter: {polygon_diameter(hull):.3f}') # 5.0 (diagonal)
Applications
Rotating calipers enables O(n) solutions (after O(n log n) hull construction) for: - Diameter: Maximum distance between hull vertices - Minimum width: Minimum enclosing strip - Minimum enclosing rectangle: Smallest bounding rectangle - Closest pair between two convex hulls: O(n+m) - Intersection of convex hulls: O(n+m)
All of these would be O(n²) or O(n²m) without the rotating calipers insight.
🎯 Key Takeaways
- Rotating calipers: O(n) scan of antipodal vertex pairs after O(n log n) convex hull. Reduces many O(n²) problems to O(n).
- Each vertex is antipodal to O(1) others as we rotate 360° — the total antipodal pairs is O(n).
- Applications: diameter, minimum width, minimum bounding rectangle, closest pair between hulls.
- Always build convex hull first — rotating calipers only works on convex polygons.
Interview Questions on This Topic
- QWhat is an antipodal pair and why does rotating calipers only need to check O(n) pairs?
- QHow would you find the minimum bounding rectangle of a point set?
- QWhat is the time complexity of rotating calipers and why?
Frequently Asked Questions
Does rotating calipers work on non-convex polygons?
No — rotating calipers requires a convex polygon. For non-convex polygons, compute the convex hull first (O(n log n)), then apply rotating calipers to the hull. The hull has at most n vertices, so the total complexity remains O(n log n).
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.