The farthest pair problem starts with a discouraging ledger.

Given \(n\) points in the plane, there are:

\[\binom{n}{2}\]

distances to check. That is fine for a toy scatterplot and boringly expensive for a geometry kernel.

But the farthest pair has a useful embarrassment: it cannot hide in the middle.

If point \(p\) is strictly inside the convex hull, and \(q\) is some other point, extend the ray from \(q\) through \(p\) until it hits the hull boundary at \(p'\). Then:

\[\|p' - q\| > \|p - q\|.\]

So an interior point cannot be a unique endpoint of the diameter. The search belongs on the convex hull.

That reduces the problem from “all points” to “all hull vertices.” It does not yet explain why the remaining search can be linear in the number of hull vertices.

The missing word is antipodal.

Support Lines Name The Candidates

For a convex polygon, a support line is a line that touches the polygon while the whole polygon lies on one side of it. Two vertices are antipodal if there are parallel support lines through them.

A diameter pair must be antipodal. If two farthest vertices did not admit parallel supports perpendicular to the segment between them, one endpoint could slide along the hull to make the segment longer. The exact proof is a standard convexity argument; the useful engineering consequence is simpler:

do not compare every hull pair
compare the pairs exposed by parallel supports

Shamos used this idea in his 1978 thesis to compute the diameter of a convex polygon in linear time. Toussaint later named and generalized the method as “rotating calipers”: rotate support lines around the polygon and emit the antipodal pairs encountered along the way.1 Toussaint’s 1983 paper describes the diameter procedure as generating all \(O(n)\) antipodal vertex pairs and taking the largest distance among them.2

The picture is literal enough to be useful. Put one caliper blade along a hull edge. Put the parallel blade against the opposite supporting vertex. Rotate the edge blade to the next hull edge. The opposite vertex may need to advance, but it never needs to go backward.

The Area Test Replaces Angles

The lab below uses Andrew’s monotone-chain hull construction: sort points lexicographically, scan the lower and upper chains, and pop the last chain vertex whenever it would make the wrong turn. The paper is short; CGAL’s bibliography records Andrew’s 1979 Information Processing Letters citation as “Another efficient algorithm for convex hulls in two dimensions.”3

Once the hull is in counterclockwise order, the caliper walk can avoid measuring angles. For edge \(h_i h_{i+1}\), keep an opposite index \(j\). Advance \(j\) while the triangle area keeps increasing:

\[\left|\operatorname{cross}(h_{i+1}-h_i,\; h_{j+1}-h_i)\right| > \left|\operatorname{cross}(h_{i+1}-h_i,\; h_j-h_i)\right|.\]

Area here is just base times height. If the next vertex is farther from the current support line, the opposite blade has not reached its support position yet.

The algorithm has a small but important asymmetry:

for each hull edge i -> i+1:
    while opposite vertex j+1 is farther from the edge line:
        j = j + 1
    test candidate pairs involving edge endpoint(s) and j

Index \(i\) moves once around the hull. Index \(j\) also moves once around the hull. The loop is nested syntactically, but not quadratically.

That monotonicity is the algorithm.

The Browser Lab

The lab generates deterministic point sets, computes a monotone-chain hull, runs the rotating-calipers diameter walk, and checks the result against exhaustive all-pairs search over the original points.

In the default run, 44 generated points produce 14 hull vertices. Exhaustive search over the original points checks 946 distances. The caliper candidate ledger checks 14 hull pairs and reports the same diameter.

Move the Caliper step slider. Amber marks the current hull edge’s support line. The dashed green line is the parallel support through the current opposite vertex. The red chord is the best diameter found by the walk.

The important behavior is not the red line. It is the green vertex: as the orange edge moves around the hull, the opposite support vertex advances forward. The nested while loop has no chance to restart from zero.

Reproducibility Check

The browser lab is also a CommonJS module. From the repository root:

node - <<'NODE'
const lab = require("./assets/js/rotating-calipers-lab.js");
const EXPECTED_SHAPES = ["cloud", "crescent", "rectangle", "clusters", "thin"];
const EXPECTED_COUNTS = [8, 17, 31, 64, 96];
const EXPECTED_SEEDS = [1, 7, 23, 91];
const EXPECTED_CASE_KEYS = EXPECTED_SHAPES.flatMap((shape) =>
  EXPECTED_COUNTS.flatMap((count) =>
    EXPECTED_SEEDS.map((seed) => `${shape}/${count}/${seed}`)
  )
);
const EXPECTED_TOTALS = {
  caseRows: 100,
  checked: 800,
  criticalRows: 8,
  passed: 100,
  total: 100,
  passedChecks: 800,
  totalChecks: 800
};
const EXPECTED_BY_SHAPE = [
  "cloud:20:20:160/160:hull=12.900:cand=12.900:brute=1441.000",
  "crescent:20:20:160/160:hull=11.700:cand=11.900:brute=1441.000",
  "rectangle:20:20:160/160:hull=10.950:cand=10.950:brute=1441.000",
  "clusters:20:20:160/160:hull=7.400:cand=7.400:brute=1528.400",
  "thin:20:20:160/160:hull=9.000:cand=9.000:brute=1528.400"
];
const EXPECTED_CRITICAL_CHECKS = [
  "all generated points are inside the hull:100/100:true:none",
  "brute-force diameter endpoints are hull vertices:100/100:true:none",
  "calipers diameter matches all-pairs brute force:100/100:true:none",
  "calipers inspected only a linear number of candidates:100/100:true:none",
  "candidate ledger contains the chosen best pair:100/100:true:none",
  "hull has at least two endpoints when the input does:100/100:true:none",
  "hull orientation is convex:100/100:true:none",
  "selected event is valid:100/100:true:none"
];

function sameJson(actual, expected) {
  return JSON.stringify(actual) === JSON.stringify(expected);
}

const audit = lab.auditGrid();
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const totals = {
  caseRows: audit.cases.length,
  checked: audit.checked,
  criticalRows: audit.criticalChecks.length,
  passed: audit.passed,
  total: audit.total,
  passedChecks: audit.passedChecks,
  totalChecks: audit.totalChecks
};
const caseKeys = audit.cases.map((row) => `${row.shape}/${row.count}/${row.seed}`);
const byShapeRows = audit.byShape.map((row) =>
  `${row.shape}:${row.cases}:${row.passed}:${row.passedChecks}/${row.totalChecks}:` +
  `hull=${row.avgHull.toFixed(3)}:cand=${row.avgCandidates.toFixed(3)}:` +
  `brute=${row.avgBrutePairs.toFixed(3)}`
);
const criticalRows = audit.criticalChecks.map((row) =>
  `${row.check}:${row.passed}/${row.total}:${row.ok}:` +
  `${row.failedCases.join(",") || "none"}`
);
const caseKeyErrors = caseKeys
  .map((actual, index) =>
    actual === EXPECTED_CASE_KEYS[index]
      ? null
      : { index, actual, expected: EXPECTED_CASE_KEYS[index] }
  )
  .filter(Boolean);
if (caseKeys.length !== EXPECTED_CASE_KEYS.length) {
  caseKeyErrors.push({
    index: "length",
    actual: caseKeys.length,
    expected: EXPECTED_CASE_KEYS.length
  });
}
const auditShape = {
  totals,
  byShapeRows,
  criticalRows,
  caseKeyErrors,
  caseKeyHead: caseKeys.slice(0, 10),
  caseKeyTail: caseKeys.slice(-10)
};
const shapeErrors = [
  sameJson(totals, EXPECTED_TOTALS) ? null : "totals",
  caseKeyErrors.length === 0 ? null : "caseKeys",
  sameJson(byShapeRows, EXPECTED_BY_SHAPE) ? null : "byShapeRows",
  sameJson(criticalRows, EXPECTED_CRITICAL_CHECKS) ? null : "criticalRows"
].filter(Boolean);
const displayRows = audit.byShape.map((row) => ({
  shape: row.shape,
  cases: row.cases,
  avgHull: row.avgHull.toFixed(1),
  avgCandidates: row.avgCandidates.toFixed(1),
  avgBrutePairs: row.avgBrutePairs.toFixed(1),
  passed: row.passed,
  checks: `${row.passedChecks}/${row.totalChecks}`
}));
console.table(displayRows);
console.table(audit.criticalChecks);
if (shapeErrors.length) {
  throw new Error(
    `rotating-calipers audit shape drifted in ${shapeErrors.join(", ")}:\n` +
    JSON.stringify(auditShape, null, 2)
  );
}
const summary =
  `${audit.passed}/${audit.total} cases and ${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  failed.length ||
  !audit.ok ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(`${summary}: ${JSON.stringify(failed, null, 2)}`);
}
console.log(summary);
NODE

The current audit grid has 100 deterministic cases and 800 individual checks: five point-set families, five point counts, and four seeds. Each case verifies:

  • the monotone-chain hull is convex;
  • every generated point lies inside or on the hull;
  • the brute-force farthest pair over all generated points has both endpoints on the hull;
  • the caliper diameter matches all-pairs brute force;
  • the caliper candidate ledger is linear in the hull size; and
  • the selected visualization event is a real event from the computed walk.

The implementation is intentionally small: assets/js/rotating-calipers-lab.js.

Where The Toy Stops

The lab uses ordinary JavaScript floating-point arithmetic and synthetic point sets. That is fine for teaching the shape of the algorithm. It is not enough for a production geometry kernel.

Convex hull construction and caliper advancement both depend on orientation predicates: the sign of a cross product. Near-collinear points can make that sign numerically fragile. Shewchuk’s robust-predicate work is the classic software answer: use fast floating-point filters and adaptive exact arithmetic when the sign is too close to call.4

Degeneracy policy also matters. Do collinear boundary points stay in the hull or get compressed into one edge? If several opposite vertices tie for the same support line, which candidate pairs are emitted? The lab removes collinear middle vertices in the hull and adds tie candidates when parallel supports are detected. A library has to specify that policy, test it, and keep it stable.

Finally, rotating calipers is not magic for every geometric distance. Toussaint’s paper emphasizes the generality of the method for many convex-polygon problems, but also notes that some natural-looking variants do not reduce to antipodal vertex pairs.2 The method works when the geometric optimum is exposed by moving support lines.

For the diameter of a finite planar set, that exposure is exactly what we need:

all points -> convex hull -> antipodal candidates -> longest chord

The quadratic ledger was real. The hull just knew which rows could not win.

  1. Godfried T. Toussaint, “The Rotating Calipers”, McGill Computational Geometry Lab. The page credits Michael Shamos’s 1978 thesis for the original diameter method and Toussaint’s 1983 paper for the name and generalization. ↩

  2. Godfried T. Toussaint, “Solving Geometric Problems with the Rotating Calipers”, Proceedings of IEEE MELECON’83, Athens, Greece, May 1983. ↩ ↩2

  3. A. M. Andrew, “Another efficient algorithm for convex hulls in two dimensions,” Information Processing Letters 9(5):216-219, 1979. See the CGAL 2D Convex Hulls bibliography. ↩

  4. Jonathan Richard Shewchuk, “Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates”, Discrete & Computational Geometry 18:305-363, 1997. Project page: “Fast Robust Predicates for Computational Geometry”. ↩