Andrew's monotone chain sweeps the points in sorted order and pops from a stack whenever the last three do not turn left. Swap the exact predicate for the double-precision one and change nothing else: on the needle triple the exact chain returns three vertices and the double chain returns two. The lost corner is not recoverable downstream, because the hull that comes back is a perfectly well-formed hull of the wrong set.
Core ideas
The algorithm first, because the failure is a consequence of exactly one line of it; then what the pop does; then why nothing later can repair it.
Sort the points by x then y. Walk them left to right keeping a stack; before pushing the next point p, pop while the last two on the stack and p fail to turn left. Then walk back right to left doing the same, and concatenate the two chains without their duplicated endpoints. The whole algorithm is a sort and that one comparison, which is why swapping the comparison is a clean experiment: everything else is identical.
The condition is orient(s₂, s₁, p) ≤ 0, so a determinant of zero pops. That is the right convention with exact arithmetic — it discards points that lie strictly inside an edge, which are not vertices. With a rounded determinant it is a catastrophe, because a genuine corner whose determinant rounded to zero is popped off and never looked at again. The lab's step-by-step trace shows the pop happening at a numbered step.
The hull the double predicate returns is a convex polygon with all its vertices among the input points. It passes every sanity check a downstream consumer would think to apply. The only way to know it is wrong is to compare it against the definition, and the lab does: every point is independently classified as a vertex, a boundary point or an interior point by rotating a separating line about it, with no sort and no stack anywhere in that computation.
The material
The chain, the pop condition, the trace where the corner goes, and the definition that referees the two answers.
Sort the distinct points lexicographically by x then y. Build the lower chain by scanning left to right: maintain a stack, and before pushing p, repeatedly pop the top while the stack has at least two points and orient(s₂, s₁, p) ≤ 0, where s₁ is the top and s₂ the one below it. Build the upper chain the same way over the reversed order. The hull is the two chains concatenated with each one's last point dropped, since it is the other's first.
The sort costs n log n and dominates; the scan is linear, because each point is pushed once per chain and popped at most once per chain. The two chains between them push exactly 2n times and pop no more than they pushed, so the stack work is at most 4n operations. On the square-with-midpoints example further down this course the lab measures 18 pushes and 12 pops, and 30 operations is inside the 36 that argument allows.
With an exact orientation predicate, the monotone chain returns exactly the vertices of the convex hull of the input, in counter-clockwise order, each once. Points strictly inside the hull and points lying in the interior of a hull edge are both excluded.
Take the lower chain. Its invariant is that the stack is a sequence of points increasing in x that turns strictly left at every interior point of the sequence. The pop loop restores that invariant before each push, and a push of a point with larger x cannot violate the part of the sequence below it.
At the end, every point of the input lies on or above the lower chain: if some point were below it, it would have been scanned at its own turn and would have popped whatever lay above it. So the lower chain is the lower boundary of the hull, and its interior points are exactly the hull vertices whose neighbours lie to either side in x.
The upper chain is the mirror image and gives the upper boundary. Their concatenation is the boundary of a convex polygon whose vertices are the points at which it genuinely turns, because the pop condition was ≤ 0 and so removed every point at which it does not.
□
Take the needle triple (0, 0), (134217729, 134217728), (134217728, 134217727). Sorted, it is (0, 0), then (134217728, 134217727), then (134217729, 134217728). The exact determinant of those three in that order is +1, a left turn, so the lower chain pushes all three and the hull has 3 vertices. The double determinant of the same three is 0, which satisfies ≤ 0, so the middle point is popped at step 3 and the hull comes back with 2. The lab prints both counts side by side and labels the shortfall.
Read the two traces beside each other in the lab's lower table. The exact run is push (0, 0), push (134217728, 134217727), push (134217729, 134217728) on the lower chain: six pushes and one pop across both chains. The double run is push (0, 0), push (134217728, 134217727), then POP (134217728, 134217727), then push (134217729, 134217728). One extra pop, one fewer vertex, and the pop is at the step where the rounded determinant was consulted.
Suppose the hull is fed to the rotating-calipers diameter computation, or to a point-in-polygon test, or to anything else that consumes a hull. It receives a convex polygon on two of the three points. Every invariant it would check holds: the points are input points, the polygon is convex, the winding is consistent. The consumer has no evidence that anything is missing, and the diameter it computes will be a real distance between two real points — just not the right one when the missing corner was an endpoint.
This is the argument for exact predicates stated as a number rather than as a principle. It is not that floating point is imprecise; it is that a predicate returning a discrete answer either returns the right discrete answer or corrupts the data structure built on it, and there is no third option and no amount of downstream care that recovers it.
The page does not decide which hull is right by trusting either chain. Before either algorithm runs, every point is classified from the definition: p is a hull VERTEX when some line through p has every other point weakly on one side and every point lying ON that line strictly beyond p along it. That is a cubic-time test with no sort, no stack and no incremental step in it, and the colours in the drawing come from it rather than from either algorithm.
So the table in the middle of the lab is a comparison and not a restatement. On the needle triple the definition says all three points are vertices, the exact chain agrees, and the double chain is one short — and the row for the missing point is marked. If the chain and the definition ever disagreed, the status line would say so in red and decline to pick a winner, because a page that reports two exact routes disagreeing is not entitled to guess which one is broken.
Interactive
Two algorithms and two predicates, refereed by the definition itself
Method
Change one thing, and make sure the referee is not one of the things you changed.
Same points, same sort, same stack, same pop condition. The lab's two arms are literally the same function with the comparison passed in as an argument, which is the only way the difference in the answer can be attributed to the comparison.
The two hulls on the needle triple differ by one vertex out of three, and at this aspect ratio the drawing cannot show it: the three points are collinear to the width of a pixel. The counts differ, the table's row for the missing point is marked, and neither fact is visible in the picture.
The brute-force classification from the definition is the referee. Where the chain and the definition agree, the page says so; where they do not, it says that too and stops. An experiment whose referee is one of the two arms has established nothing.
Type points with small coordinates and switch the predicate back and forth: the two counts stay equal. That is the control. Without it, “the double predicate gives a different answer” could just as well be a bug in how the second arm was wired up.
The points sorted are (0, 0), (134217728, 134217727), (134217729, 134217728). Call them A, B, C. Only the lower chain differs between the two runs.
The pop at step 3 is the entire defect. Every other step of the two runs is identical, and the eighth step in the double run exists only because the third one removed a point that had to be pushed again later. A reader watching the counts alone would see 3 against 2; a reader watching the trace sees the exact moment and the exact comparison responsible.
Notice that B is popped from the UPPER chain in both runs, at step 6 and step 7 respectively. That is correct and has nothing to do with rounding: the upper chain visits the points right to left, and on this triple B is below the line from C to A, so it belongs to the lower boundary and not the upper one. Only the lower-chain pop is the failure.
For a faded rehearsal, work out what the two runs do on (0, 0), (67108865, 67108864), (67108864, 67108863), which is the same shape one power of two smaller. The supplied first move is from the previous lesson: at 2²⁶ the two products are both under 2⁵³, so the double determinant is +1 as well. Predict both traces, then check that the lab reports 3 and 3.
You should be able to state the pop condition and why it uses ≤, trace both runs on the needle triple and name the step where they diverge, explain why the wrong answer passes every structural check, and say which defects the one-sidedness theorem permits and which it forbids.
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.