The convex hull is the smallest convex set containing the points, and its vertices are the points that cannot be written as combinations of the others. The lab computes that definition directly, by rotating a separating line about each point, and uses it as the referee for Andrew's monotone chain and for gift wrapping. On nine points in general position all three agree on the same four corners, and the two algorithms' costs do not resemble each other at all.
Core ideas
A definition that mentions no algorithm, a test that computes it directly, and two algorithms whose costs are quoted in different quantities.
The convex hull of a finite point set is the smallest convex set that contains it — equivalently, the intersection of every half-plane containing all the points, or the set of all weighted averages of them. None of those mentions sorting, stacking or wrapping. A vertex is a point of the set that is not in the hull of the others, so removing it changes the hull and removing any other point does not.
p is outside the hull of the others exactly when some line through p has all of them weakly on one side, with every point lying ON that line strictly beyond p along it. That second clause is what separates a corner from a point sitting in the middle of an edge. The lab tests it by taking the line through p and each other point in turn, which is enough: rotate a separating line about p until it first touches the set.
The monotone chain sorts and then makes a linear pass, so it costs n log n regardless of the answer. Gift wrapping walks from vertex to vertex, doing n work to find each one, so it costs n·h where h is the number of hull points — a quantity that is not known until the algorithm finishes. On these nine points the lab measures 36 comparisons for gift wrapping and prints n log₂ n = 27 beside it for reference.
The material
Three equivalent definitions, the separating-line test, and the two algorithms measured against each other and against the definition.
The convex hull of a finite set S is the smallest convex set containing S. Equivalently it is the intersection of all half-planes containing S, and equivalently the set of all convex combinations of points of S. A point p ∈ S is a vertex of the hull when p is not in the convex hull of S minus p, and a boundary point when p lies on the hull's boundary. Every vertex is a boundary point; the converse fails exactly where three points of S are collinear.
Those three descriptions are genuinely the same set, and it is worth knowing which one to reach for. “Smallest convex set” is the one to use when arguing that some construction returns the hull. “Intersection of half-planes” is the one that turns into a separating-line test. “Convex combinations” is the one that makes “p is not a vertex” mean something concrete: p is an average of other points of the set.
Let p ∈ S and let T = S minus p. Then p is a hull vertex of S if and only if there is a line through p such that every point of T lies weakly on one side of it, and every point of T lying on the line lies strictly beyond p along the line. Moreover, if such a line exists then one exists that passes through p and some point of T.
If p is a vertex, then p is not in the convex hull of T, which is a compact convex set, so by the separating hyperplane theorem there is a line strictly separating p from it. Translate that line to pass through p: every point of T is now strictly on one side, which is a stronger condition than the statement requires.
Conversely, suppose such a line exists. Any convex combination of points of T lies weakly on the chosen side, and if it equalled p then every point with nonzero weight would have to lie on the line itself; but all of those lie strictly beyond p along it, so their average does too and cannot be p. Hence p is not in the hull of T.
For the last part, rotate the separating line about p. Since T is finite, rotating until the line first meets a point of T preserves the one-sidedness, and the point it meets satisfies the beyond-p clause because it was strictly on one side before the rotation. So testing the n − 1 lines through p and each other point suffices, which is what makes this a finite check.
□
That last paragraph is why the lab can compute the definition at all. A quantifier over every line through p is not something a browser can evaluate; a quantifier over the n − 1 lines through p and another point is a loop. The whole test is cubic in the number of points, which is extravagant and exactly right for a referee: it shares no code, no data structure and no idea with either algorithm it is judging.
The lab opens on (0, 0), (6, 0), (6, 6), (0, 6), (3, 3), (2, 1), (4, 5), (1, 4), (5, 2) — a square with five points scattered inside it. The definition marks four of them as vertices and four as boundary points, which is the same four: no point of this set lies in the interior of a hull edge. The monotone chain returns those four, gift wrapping returns those four, and the table's four columns agree row by row.
One correction to make while looking at that input: these nine points are NOT in general position, although both the worked example's own label and the status line under the widget say they are. Four collinear triples exist among them — (0, 0), (3, 3), (6, 6), and three more through that same centre point. What the page is entitled to say, and what actually matters here, is narrower: none of those triples puts a point between two hull vertices, so the boundary set and the vertex set coincide and the two algorithms cannot be told apart on this input. Collinearity strictly inside the hull is invisible to both of them.
The chain's work is a sort plus a linear scan. The lab counts the scan: on these nine points, 18 pushes and 12 pops, 30 stack operations in all. Each chain pushes every point exactly once, so the two together push 2n = 18, and neither can pop more than it pushed, so the ceiling is 4n = 36. The sort is not counted here because Sorting and Selection already costed it.
The widget's own stack figure reads “18 + 12 = 30 against 2n = 18”, and the caption above its trace says the two chains cost 2n stack operations and no more. Take the 4n in the previous paragraph instead: 2n is the number of PUSHES, since each chain pushes each point once, and the pops are a second 2n at worst. The measured 30 is genuinely below its ceiling, and the ceiling is 36. A reference figure smaller than the measurement beside it is always worth checking rather than believing, which is the habit this whole path is trying to install.
Gift wrapping does something quite different: from the current vertex it scans all n points to find the next one, and repeats until it returns to the start. Its work is therefore n per hull vertex. The lab reports 36 comparisons on this input and prints n·⌊log₂ n⌋ = 27 beside it as a reference column. Here the output-sensitive algorithm is doing MORE work than the sort-based bound, because h = 4 is not small enough relative to log₂ 9 to pay for the difference.
n·h beats n log n when h is smaller than log n, and on nine points log₂ 9 is about 3.17 while h is 4. So the reference column is larger than the measured count, and the lesson is not that gift wrapping is a bad algorithm: it is that its advantage is a claim about inputs whose hull is tiny relative to their size, and this input is not one of them. Type a thousand points inside a triangle and the ratio inverts.
This is the shape every page on this path takes. The measured number and the bound sit in the same row, they disagree, and the disagreement is explained rather than hidden. The reference column carries no verdict and the page says so: it is a drawing of a function, evaluated at the n on screen. It is not hard to make the comparison go the other way either — 24 points with only three on the hull give n·h = 72 against the same reference at 96.
One last thing to type into the box, because it is why Sorting and Selection is a prerequisite for this course. Enter 5, 25; 1, 1; 9, 81; 3, 9; 7, 49, which is the numbers 5, 1, 9, 3, 7 each lifted to (x, x²). All five come back as hull vertices, and the lower chain reads (1, 1), (3, 9), (5, 25), (7, 49), (9, 81) — the inputs in sorted order. Any hull algorithm therefore sorts, so the comparison lower bound proved there applies here unchanged, and the monotone chain's n log n is not an implementation choice a cleverer method could avoid.
Interactive
Two algorithms and two predicates, refereed by the definition itself
Method
Answer the definition's question about each point, then compare with whatever the algorithm returned.
Both hull algorithms misbehave on a repeated point: the chain can return it twice and gift wrapping does. The lab removes duplicates before anything else and reports how many, because that count is information about the input and not an implementation detail to hide.
For each p, look for a line through p and one other point with everything else weakly on one side. If you find one, and every point on that line is beyond p, then p is a corner. This is slow and it is not how you would compute a hull; it is how you check one.
Two answers of the same size can still be different sets. The lab compares the sorted keys of the two point lists, and the per-point table shows which run included which point, so a swap of one vertex for another is visible rather than hidden behind a matching total.
The stack count and the gift-wrapping work are counts on the points on screen. Change the input and both move; change it so that everything is inside a triangle and they move in opposite directions. Neither number is a bound and the page never calls one.
The points are (0, 0), (6, 0), (6, 6), (0, 6), (3, 3), (2, 1), (4, 5), (1, 4), (5, 2). For each one, look for a line through it with everything else on one side.
The four interior points are interior for different reasons, and it is worth seeing that the test does not care. (3, 3) is the centre and lies on two diagonals; (2, 1) is near an edge; (4, 5) is near a corner. Every line through any of them has points of the set strictly on both sides, and that is the whole verdict.
The two cost figures are the interesting part of this table. The chain's 30 stack operations are a count of work it actually did; the 36 gift-wrapping comparisons are the same; and the 27 beside them is n times the integer part of log₂ n, which is a function evaluated at n = 9 and not a measurement of anything. Reading “36 against 27” as “gift wrapping is 33 per cent worse” would be comparing a count with a drawing.
For a faded rehearsal, delete (3, 3) and predict every figure in the table before rerunning. The supplied first move is that the four corners are unaffected: (3, 3) is in the hull of the others, so removing it cannot change which points are vertices. Say what happens to the 18, the 12 and the 36, and then say why one of those three does not move in proportion to the other two.
You should be able to give the three equivalent definitions and say which is useful for what, prove or reconstruct the separating-line characterisation including why lines through pairs suffice, and read the two cost columns as a measurement and a reference respectively.
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.