The two furthest-apart points of a set are both hull vertices, so the sixteen-point cloud in the lab reduces to a four-vertex square before anything is measured. The rotating calipers then walk the hull once and examine only antipodal pairs — four of them here, against 120 pairs of points. The answer is a squared distance, which is an integer, and two different pairs attain it.
Core ideas
One reduction, one walk, and one honest remark about what the saving depends on.
If q is strictly inside the hull then it is a convex combination of hull vertices, and for any other point r at least one of those vertices is at least as far from r as q is. So no interior point can be an endpoint of the longest segment, and the diameter of the set is the diameter of its hull. On the lab's sixteen-point cloud that discards twelve points before any distance is computed.
A pair of hull vertices can be the diameter only if they admit parallel supporting lines — if you can lay a ruler against the hull at each of them with the two rulers parallel. Such a pair is called antipodal. Walking two indices round the hull in step enumerates all of them in linear time, and there are O(h) of them rather than h(h − 1)/2. The lab reports 4 on the cloud, against 120 pairs of input points.
No square root is taken anywhere. The squared distance between lattice points is an integer, comparing squared distances orders pairs exactly as comparing distances does, and so the comparison that picks the winner never rounds. On the cloud the squared diameter is 225 and two different pairs attain it, so the ANSWER is a value and the pair printed is one of several — a distinction the page makes explicitly rather than leaving to the reader.
The material
The reduction, the antipodal characterisation, the measured counts, and the input where the saving vanishes.
The diameter of a finite set is the largest distance between two of its points. Two points u, v of a convex polygon are an antipodal pair when there exist parallel supporting lines of the polygon, one through u and one through v — that is, lines touching the polygon with the whole polygon on one side of each.
Let S be a finite set with at least two points and let u, v attain its diameter. Then u and v are both vertices of the convex hull of S, and they are an antipodal pair of that hull.
Suppose u is not a hull vertex. Then u is a convex combination Σ λᵢ pᵢ of other points. The function x ↦ |x − v| is convex, so |u − v| ≤ Σ λᵢ |pᵢ − v|, and therefore some pᵢ is at least as far from v as u is. That pᵢ is a different point, so the pair (pᵢ, v) also attains the diameter, and repeating the argument reaches a hull vertex. The same runs for v.
For antipodality, let ℓᵤ be the line through u perpendicular to the segment uv, and ℓᵥ the line through v perpendicular to it. These are parallel. If some point w of S lay strictly on the far side of ℓᵤ from v, then |w − v| would exceed |u − v|, contradicting the diameter; so everything is weakly on one side of ℓᵤ, and likewise for ℓᵥ. Both are therefore supporting lines, and u, v are antipodal.
□
That proof is the whole justification for the algorithm and it is worth noticing what it does NOT say. It does not say every antipodal pair is a candidate worth examining because it is nearly the diameter; it says the diameter is among them, so examining all of them suffices. The calipers are an exhaustive search over a set that has been proved to contain the answer, which is why they can be confident rather than heuristic.
The lab's cloud is the four corners of a 12-by-9 rectangle plus twelve points scattered inside it. The hull is the rectangle, h = 4, and the calipers examine 4 antipodal pairs. The squared diameter is 225, between (0, 0) and (12, 9) — and also between (12, 0) and (0, 9), since 12² + 9² = 225 either way. Testing all 16·15/2 = 120 pairs of input points returns the same value.
The two figures to hold on to are 4 and 120. The brute force is run on every redraw, on the same points, because an algorithm that visits the wrong pairs returns a distance that is real and simply not the largest — there is no internal inconsistency for it to trip over. As with the hull, the check is a different computation and not a second opinion from the same one.
Once the hull is built, the twelve interior points are never looked at again. That is where the reduction from 120 to 4 comes from, and it is worth being precise that the hull itself was not free: it cost a sort. The honest statement is that the diameter of n points costs a hull plus O(h), which is O(n log n) in total, against O(n²) for the scan. On sixteen points neither of those constants means much, and the page prints counts rather than claiming a speed.
Take eight points in convex position — the lab has one such preset — and every point is a hull vertex. The hull has bought nothing, the calipers walk the whole input, and the antipodal-pair count is 8 against 28 pairs of points. The saving is smaller and still real. Now imagine n points on a circle: h = n, the hull costs a sort and discards nothing, and the calipers' linear walk is linear in n rather than in something smaller.
So h is a property of the input, not a bound on it. The lab says this directly in its status line, and it is the geometry version of the one thing this whole path keeps insisting on: the count you just watched is a measurement of the points on screen. 4 and 120 are true about this cloud. O(n log n) is the claim about every input, and it is proved by the hull bound and the linear walk rather than by either number.
Interactive
Rotating calipers against every pair, with the distance left squared
Method
Reduce to the hull, walk the hull, and keep everything squared.
The proof licenses this completely: no interior point can be an endpoint of the longest segment. The lab reports how many points the hull kept, and on the cloud that is 4 of 16.
Advance the second index while it keeps moving away from the current edge, then advance the first. Each index goes round once, so the walk is linear in h and enumerates the antipodal pairs without ever forming a pair twice.
Squared lattice distances are integers, and a < b for nonnegative reals is the same as a² < b². So the comparison that decides the winner is an integer comparison, exactly as the orientation tests elsewhere are.
On the cloud two pairs attain 225, and on the square in the preset list two diagonals attain 72. The diameter is a value; the pair is one witness among possibly several, and a page that prints one pair without saying so invites a reader to think it is the pair.
The four corners are (0, 0), (12, 0), (12, 9) and (0, 9); the other twelve points are inside the rectangle.
The rectangle is 12 by 9, so both diagonals have squared length 144 + 81 = 225 and actual length 15. Two genuinely different pairs are at the diameter, and the calipers happen to visit each of them twice as the walk goes round. The page reports the value as the answer and names one pair as a witness.
Twelve of the sixteen points appear nowhere in this table, and that is the entire content of the reduction. They were used once, to build the hull, and then discarded on the strength of a proof rather than of a heuristic. Note that 225 is exact: no square root was taken, and the number 15 appears only in this paragraph, as a remark.
For a faded rehearsal, predict what the table becomes if you move (0, 0) to (0, 3), so that the hull is a pentagon rather than a rectangle. The supplied first move is that h rises and so does the antipodal-pair count; the squared diameter, however, is now 12² + 9² = 225 between (12, 0) and (0, 9) alone. Say how many pairs attain it, and check whether the number of pairs of input points changed at all.
You should be able to prove that the diameter is attained by hull vertices, explain what makes a pair antipodal and why those are the only candidates, work with squared distances throughout, and read h as a measurement of the input rather than as a bound.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.