Rotating Calipers

Advance antipodal support lines around a convex polygon to find its diameter without checking every pair.

Core idea

On a convex polygon, an antipodal support point moves monotonically as each hull edge advances. This rotating pair visits all diameter candidates without restarting a scan.

Read the visualization

One pointer selects the current hull edge and the other rotates while triangle area increases. Candidate endpoint distances update the best diameter pair.

Load the convex polygon and place the first antipodal support pair.

1function diameter(hull: Pt[]): number {
const m = hull.length;
const area2 = (a: Pt, b: Pt, c: Pt) => Math.abs(cross(a, b, c));
let j = 1, best = 0;
for (let i = 0; i < m; i++) {              // init count  convex hull  edge init
  const ni = (i + 1) % m;
  while (area2(hull[i], hull[ni], hull[(j + 1) % m]) >
         area2(hull[i], hull[ni], hull[j])) {
    j = (j + 1) % m;                       //  advance the antipodal point monotonically (spin → spin)
  }
  best = Math.max(best, d2(hull[i], hull[j]), d2(hull[ni], hull[j])); // spin candidate 
}
return best;                               //  diameter ²( one done)
14}

convex hull vertex6

current farthest ²-

1 / 8

Complexity and tradeoffs

Time: O(n) after the hull. Space: O(1). Monotone orientation changes ensure each pointer makes at most one full circuit.

Invariant: The opposite pointer never needs to move backward because support direction rotates monotonically around a convex polygon.

Where it fits

Rotating calipers finds convex diameter, width, bounding rectangles, and distances between convex polygons after a hull has already been built.

Algorithm Visualizer

Rotating Calipers

Core idea

Read the visualization

Complexity and tradeoffs

Where it fits