Every other entry in this category answers "what is the boundary of this point set" — Graham
Scan, Jarvis March, Monotone Chain, Quickhull, Chan's Algorithm, and Divide-and-Conquer Convex Hull
all build the same convex hull by different routes. This page asks a different question: given
that the hull already exists, what's the farthest distance between any two of its vertices — the
polygon's diameter? Checking every pair of hull vertices directly costs
O(n²). Rotating calipers finds it in O(n) instead, by treating the hull's
own edges as a rotating pair of parallel support lines and noticing that the vertex farthest from
one caliper edge only ever moves forward around the polygon as the calipers rotate —
never backward — so the whole sweep touches each vertex a bounded number of times. (A second entry,
Convex Hull Trick, asks a different question again
— given many linear functions instead of a point set, which is the maximum at a query x
— with no polygon involved at all.)
One fact worth stating plainly, since the rest of this page leans on it: the two points achieving a point set's diameter are always hull vertices, never interior points. An interior point sits strictly inside the rubber band, and moving it outward toward the boundary — in whichever direction increases distance to any fixed target — can only ever increase that distance, never decrease it. So the farthest pair in the whole set and the farthest pair among just the hull vertices are the same pair; the six entries above already did the work of narrowing the search to the hull.
Eight points, already in convex position and listed in order around the boundary — A through H. Press Step or Run to watch two pointers walk around the polygon: i (bold, on the current caliper edge) and j (the vertex currently believed farthest from that edge). At each stop, the distance between them is checked against the best found so far; then whichever pointer would gain more area by moving — the caliper edge or the opposite vertex — advances one step. Both pointers only ever move forward, and the sweep stops once i has gone all the way around.
Pick any polygon edge and ask which vertex is farthest from the line through it — that vertex is
the one a "caliper" resting on that edge would touch on the far side. As the edge advances to the
next one around the polygon, the farthest vertex can only ever advance too, or stay put; it can
never fall back to an earlier vertex, because doing so would mean the polygon dips back inward,
which a convex shape never does. That one-directional property is what turns an
O(n²) all-pairs check into an O(n) walk: instead of re-searching from
scratch for every edge, the search for the next edge's farthest vertex just continues from where
the previous edge's search left off.
Concretely, at each stop the algorithm compares two triangle areas: the area swept out by advancing the caliper edge one step, against the area swept out by advancing the opposite vertex one step. Whichever move sweeps more area is the one that keeps the calipers actually touching the hull's true extremes rather than drifting past them — area, not distance, is the quantity being compared, because it's the one that can be computed from the current triple of vertices alone without knowing in advance which pointer "should" move.
Traced directly on this page's own octagon: the true diameter, A–E at
389.49, turns up at step 2 of 8 — checked while i is still sitting on
its very first edge. The sweep has no way to know that in advance, so it keeps walking all the way
around regardless, the same shape Closest Pair of
Points' strip check has: whatever's "best so far" only becomes the final answer once the whole
structure — recursion there, pointer walk here — has actually finished.
function polygonDiameter(poly) {
const n = poly.length;
if (n === 1) return { d: 0, pair: [poly[0], poly[0]] };
if (n === 2) return { d: dist(poly[0], poly[1]), pair: [poly[0], poly[1]] };
function dist(a, b) { return Math.hypot(a.x - b.x, a.y - b.y); }
function area2(o, a, b) { return Math.abs((a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)); }
// Find the vertex farthest from the closing edge (last vertex -> first) to start both pointers.
let k = 1;
while (area2(poly[n - 1], poly[0], poly[(k + 1) % n]) > area2(poly[n - 1], poly[0], poly[k])) {
k++;
}
let best = 0, bestPair = [poly[0], poly[k]];
let i = 0, j = k;
while (i <= k && j < n) {
const d = dist(poly[i], poly[j]);
if (d > best) { best = d; bestPair = [poly[i], poly[j]]; }
// Advance whichever pointer's next step sweeps more area — that's the one still catching up.
if (j < n - 1 && area2(poly[i], poly[(i + 1) % n], poly[(j + 1) % n]) > area2(poly[i], poly[(i + 1) % n], poly[j])) {
j++;
} else {
i++;
}
}
return { d: best, pair: bestPair };
}The bounding box's diagonal is not the polygon's diameter. It's tempting to
skip the pointer walk entirely and just take the diagonal of the axis-aligned bounding box — it's
one line of code and it does upper-bound the true diameter. But the box's corners usually aren't
polygon vertices at all. Checked directly: a square rotated 45° with vertices at
(200,100), (300,200), (200,300), (100,200) has
a bounding-box diagonal of 282.84, but no two actual vertices of that square are
farther apart than 200 (the square's own diagonal) — the box's opposite corners sit in
empty space the polygon never touches.
Parallel edges can put more than one vertex tied for "farthest" at once —
a square's diameter is realized by two different diagonals simultaneously, for instance. It's
tempting to think the strict > comparison above (rather than >=)
would then skip one of the tied candidates and risk missing the true diameter on some input.
Checked directly across 20,000 random convex polygons (sizes 3–32) plus explicit squares,
rectangles, and regular polygons up to 20 sides: the strict version matches an all-pairs
brute-force check on every single trial. The tie only ever changes which antipodal pair
gets recorded as the answer, never whether the true maximum distance is found — both tied pairs are
equally far apart, so recording either one is correct.
Degenerate input still needs an explicit answer. A single point or two points
has no ambiguity about area, so the main loop's area comparisons never even run — the reference
implementation returns early for n ≤ 2 rather than letting k's search
loop or the pointer walk operate on a polygon too small for either to mean anything.
Time: O(n) once the convex hull already exists, since pointer
i and pointer j each only advance forward and each makes at most
n total steps around the polygon — no vertex is ever revisited by either pointer.
Measured directly: this page's 8-vertex octagon takes 8 total checks to find the diameter, against
the 28 pairwise comparisons (C(8,2)) a brute-force all-pairs check would need. Across
5,000 random convex polygons up to 200 vertices, the total step count never exceeded
1.65n — comfortably linear, nowhere near the O(n²) a naive check would
cost. Building the hull itself first still costs O(n log n) (see any of the six
hull-construction entries above), which dominates the overall running time — the calipers sweep
is the cheap part.
Space: O(n) to hold the hull; the pointer walk itself uses only a
constant number of extra variables.
This site's guide, Choosing a Convex Hull Algorithm, sets this entry aside up front, apart from the six pages it actually compares: it doesn't build a hull at all, it assumes one already exists and finds its diameter.