Rotating Calipers and Convex-Polygon Optimization

Antipodal Pairs

Once a point set has been reduced to its convex hull (Part 3), a surprising number of optimization questions about it — diameter, width, minimum bounding rectangle — can be answered in $O(n)$ by walking around the hull exactly once, using the rotating calipers technique (named and popularized by Preparata and Shamos' 1985 textbook; Godfried Toussaint's 1983 paper "Solving Geometric Problems with the Rotating Calipers" is the systematic reference for the whole family of techniques below).

Picture two parallel lines — the "calipers" — touching the hull on opposite sides, like a vernier caliper measuring a physical object. Two hull vertices are antipodal if there exists some direction in which one caliper touches one vertex and the parallel caliper touches the other. As the calipers rotate a full $360°$ around the hull, the set of antipodal pairs encountered changes only at a linear number of events — one caliper's contact point advances to the next hull vertex whenever the calipers become parallel to the current edge. Because both calipers together advance around the hull at most $O(n)$ times total, every antipodal pair can be enumerated in $O(n)$, without ever re-scanning from the start.

Diameter

The diameter of a convex polygon (the maximum distance between any two of its points) is always achieved by an antipodal pair — an intuitive fact once you picture rotating calipers: the farthest-apart points must be ones where the polygon "sticks out" in some direction, on opposite sides. Rather than checking all $\binom{n}{2}$ vertex pairs ($O(n^2)$), rotating calipers checks only the $O(n)$ antipodal pairs. The Rotating Calipers spotlight has the full walking implementation.

Width

The width of a convex polygon — the minimum distance between two parallel supporting lines that sandwich it — is the minimum over all directions of the polygon's extent in that direction, and it too is achieved at an antipodal vertex-edge pair (one caliper flush against an edge, the other touching a single opposite vertex), making it another $O(n)$ rotating-calipers computation rather than a continuous optimization over all possible directions.

Minimum-Area Enclosing Rectangle

A classical and non-obvious result (Freeman and Shapira, 1975) underlies the minimum-area bounding rectangle of a convex polygon:

The algorithm walks the hull once, and for each edge, computes the bounding rectangle aligned with that edge's direction (using the already-tracked width/extreme-point calipers), keeping the minimum-area result seen — a single $O(n)$ pass, not a continuous optimization.

Distance Between Convex Polygons and Minkowski Sums

The same caliper-walking idea extends to computing the minimum distance between two disjoint convex polygons — walk both hulls' calipers in sync, advancing whichever side would keep the calipers "aligned" between the two shapes. This part also introduces the Minkowski sum of two convex polygons $A \oplus B = \{a + b : a \in A, b \in B\}$ as a reusable primitive: it can be computed in $O(n + m)$ by merging the edge-vector sequences of $A$ and $B$ in angular order (itself a calipers-style linear walk), and it recurs later in this series — directly, in Part 21's configuration-space obstacle construction for motion planning, and indirectly in Part 8's polygon Boolean operations.

Visualizing the Calipers

The key invariant is monotonicity of contact. As the support direction rotates counterclockwise, no contact index needs to move backward on a convex polygon. A nested-looking while loop remains linear because each index makes at most one circuit of the hull.

For an oriented edge $a\to b$, compare opposite vertices with $|\operatorname{orient}(a,b,p)|$. The denominator $|b-a|$ is the same for every candidate against that edge, so maximizing triangle area also maximizes perpendicular distance. Advance while the next vertex increases the area; equality signals parallel support features and may require checking both pairs.

Why the Minimum Rectangle Has an Edge-Aligned Side

Imagine a tight rectangle whose sides are not flush with any polygon edge. Rotating it slightly keeps every vertex inside while decreasing one dimension faster than the other grows, contradicting minimality. At an optimum, a side therefore becomes flush with a hull edge—reducing infinitely many orientations to the polygon's finite edge directions.

Use unit vector $u$ along the current edge and perpendicular unit vector $v$. For the four extreme contacts,

$$\text{area}=(\max p\cdot u-\min p\cdot u)(\max p\cdot v-\min p\cdot v).$$

Recomputing extrema for every edge costs $O(n^2)$. Four monotonically advancing indices—left, right, top, and bottom—preserve the $O(n)$ bound.

Minkowski-Sum Intuition and Selection Guide

Walking counterclockwise around a convex polygon yields edge vectors in cyclic angular order. To form $A\oplus B$, start at the sum of the two lowest vertices and merge their edge-vector sequences just as merge sort merges sorted values. When directions tie, add both vectors together. This produces the sum boundary in $O(n+m)$ without constructing all $nm$ vertex sums.

Where This Fits

Rotating calipers is this series' first example of an $O(n)$ algorithm solving a problem that looks like it needs $O(n^2)$ or a continuous search — a pattern that recurs in sweep-line algorithms (Part 6) and trapezoidal decomposition (Part 15). It closes out this series' Unit I on planar primitives; Unit II moves from single polygons to interacting sets of segments and subdivisions, starting with the sweep line.