Rotating Calipers

Imagine gripping a convex polygon between the flat jaws of a physical caliper. If you slowly rotate the caliper all the way around the shape without letting go, you will slide across every extreme point at least once. When the jaws are widest apart, you have just found the diameter — the two vertices that are farthest from each other.

This physical intuition is the heart of rotating calipers, a computational geometry technique published by Michael Shamos in 1978. In its algorithmic form, two parallel "support lines" are initialized touching the topmost and bottommost vertices of a convex hull, and then rotated together in small angular steps. At each step the gap between the lines is measured and the maximum recorded. One full revolution costs only $O(n)$ time — a single linear pass over the polygon's n vertices.

Before rotating calipers, computing the diameter of a convex polygon required checking all $O(n^{2})$ pairs of vertices. Shamos's insight was that the extremal pair always appears as the lines co-rotate, so no pair needs to be checked twice.

Click Step to advance the calipers by one vertex at a time, or Animate to watch the full rotation. The highlighted vertex pair in red is the current candidate for the diameter; when the rotation is complete the true diameter is locked in.

<div class="controls">
  <button id="stepBtn" type="button">{{btn_step}}</button>
  <button id="animBtn" type="button">{{btn_animate}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
  <span class="sep">|</span>
  <label class="lbl">{{lbl_polygon}}
    <select id="shapeSelect">
      <option value="hex">{{opt_hexagon}}</option>
      <option value="oct">{{opt_octagon}}</option>
      <option value="irregular">{{opt_irregular}}</option>
      <option value="rect">{{opt_rectangle}}</option>
    </select>
  </label>
</div>
<canvas id="cv" width="460" height="300"></canvas>
<div class="info" id="info">{{info_initial}}</div>

* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: #fff; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; padding: .4rem 0; }
button { font: 600 13px system-ui; padding: .35rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.sep { color: #bbb; }
.lbl { font-size: .85rem; color: #444; display: flex; align-items: center; gap: .3rem; }
select { font: 13px system-ui; border: 1px solid #ccc; border-radius: 5px; padding: .2rem .4rem; }
#cv { display: block; border: 1px solid #d0d8e4; border-radius: 8px; background: #f7f9fb;
      max-width: 100%; }
.info { margin-top: .45rem; font-size: .86rem; line-height: 1.5; color: #333; min-height: 2.6em; }
.info b { color: #1d3557; }

// Code not found

Notice that the calipers only jump to the next vertex when one of the two support lines is about to touch it — the algorithm never revisits a vertex. Every vertex is processed exactly once per caliper, giving the $O(n)$ guarantee. Compare this with the $O(n^{2})$ brute-force "check every pair" approach shown in the info panel.

How fast can you find the diameter of a convex polygon, and how do we know rotating calipers achieve the best possible speed?

• Brute force checks every pair of vertices: $O(n^{2})$ distance computations — already impractical for a polygon with thousands of vertices.
• Rotating calipers run in $O(n)$ once the convex hull is available. The key insight is the concept of antipodal pairs: two vertices are antipodal if parallel support lines can simultaneously touch both. As the calipers rotate by one full turn, every antipodal pair is visited exactly once — and the diameter must be one of them.
• It is optimal. Any algorithm for this problem must inspect all n vertices at least once (otherwise it could miss an endpoint of the diameter), so Ω(n) is a lower bound. Rotating calipers match it exactly.
• The convex hull is the bottleneck. If you start from raw points rather than a pre-computed hull, you first need $O(n \log n)$ to build it. The overall pipeline is thus $O(n \log n)$, dominated by sorting.

Rotating calipers also solve many related problems in the same $O(n)$ pass: minimum-width (the narrowest pair of parallel lines enclosing the polygon), minimum bounding rectangle, and the closest pair of antipodal features — all without extra cost. The convex hull is the prerequisite; once you have it, calipers extract an entire family of geometric properties for free.

"Find the extremal geometry of a convex shape efficiently" is a surprisingly common task in software systems:

• Robotics and collision detection: the minimum bounding rectangle of an obstacle — computed via rotating calipers — is a fast first-pass proxy for whether two objects might collide.
• Geographic information systems: axis-aligned and oriented bounding boxes for spatial queries over polygons rely on the same one-pass extremal scan.
• Computer vision: the diameter and minimum enclosing rectangle of a detected object region are used for shape classification and pose estimation.
• Computational geometry pipelines: rotating calipers are a subroutine in algorithms for the closest pair of points, Minkowski sum computation, and polygon intersection tests.
• Manufacturing and packing: the minimum-width direction tells a factory the optimal orientation to cut a part from sheet material with the least waste.

The algorithm's elegance lies in reducing a two-dimensional sweep to a one-dimensional scan along the polygon boundary. Once the convex hull exists, calipers give you diameter, width, and bounding rectangle in a single $O(n)$ pass — all three results for the price of one rotation.

Rotating calipers are a lesson in listening to the geometry. The diameter of a convex polygon cannot hide — it must be an antipodal pair, and all antipodal pairs parade past in a single $O(n)$ rotation. By exploiting that structure, Shamos turned an $O(n^{2})$ brute-force sweep into a clean linear pass.

The deeper message is algorithmic: the best solutions are often found not by working harder but by identifying the invariant that limits where the answer can be. Here the invariant is convexity — and two spinning lines are enough to harvest it completely.

Next time you need the width, diameter, or bounding rectangle of a convex shape, remember: you don't have to check every pair. Just spin the calipers once.