Lesson · Geometric Algorithms · Convex hulls and degeneracy

Three Right Answers on a Square with Midpoints

A collinear point on the boundary is not an edge case to exclude; it is a question about what you meant by “the hull”. The monotone chain returns the four corners, the boundary oracle returns all eight boundary points, and gift wrapping returns six — two of the four midpoints and not the other two, because its tie-break is the order the points were sorted in. None of the three is a bug, and only one of them is a vertex list.

Open the interactive lesson Practice

square plus a midpoint per side: 9 points typed, 9 distinct monotone chain 4 the vertices boundary oracle 8 every point on the boundary gift wrapping 6 a boundary walk whose tie-break is the sort order gift wrapping keeps (2, 0) and (4, 2); it drops (2, 4) and (0, 2) duplicates are removed and counted before any of the three runs

Nine points, three procedures, and three different counts

Core ideas

What this lesson establishes

Two questions that sound like one, a third procedure that answers neither exactly, and the reason a course should show all three rather than pick one.

Vertex and boundary are different questions

A point is a boundary point when some line through it has every other point on one side. It is a vertex when, in addition, every point ON that line is strictly beyond it. A midpoint of a side satisfies the first and fails the second: the line along that side has everything on one side of it, but the two corners of the side lie on the line in opposite directions. So the midpoint is on the boundary and is not a corner, and on this input there are four such points.

Gift wrapping walks the boundary, and its tie-break decides what it reports

Wrapping repeatedly asks “which point makes the most clockwise turn from here”. When several points are collinear with the current one, they all give the same determinant, and which of them is chosen is decided by the order the scan happens to reach them — here, the lexicographic sort order. On this square that keeps (2, 0) and (4, 2) and drops (2, 4) and (0, 2). The result is a correct boundary walk and an arbitrary subset of the collinear boundary points.

Deduplication is the lesson, not the workaround

A point typed twice breaks both algorithms: the chain can return it twice and gift wrapping does. The lab removes duplicates first and reports the count, and that count is a genuine fact about the input. Hiding it would make the two algorithms look robust on an input they are not robust on.

The material

One input, three procedures, and what each one is answering

The two definitions, the wrapping tie-break, the counts the lab measures, and why the disagreement is pinned rather than fixed.

Definition · Boundary point and vertex, side by side

For a finite set S and p ∈ S, say p is a boundary point when some line through p has every point of S weakly on one side, and a vertex when in addition every point of S lying on that line lies strictly beyond p along it. Vertices are boundary points. The two sets differ exactly at points lying in the relative interior of a hull edge.

Both questions are legitimate and different consumers want different answers. A renderer drawing the hull wants the vertices, because a polygon with a redundant collinear vertex draws the same shape and costs more. A point-location structure may want every boundary point. A convex-position test wants to know whether the two sets are equal to the whole input. The error is not choosing one; it is not saying which you chose.

Example · The square with a midpoint on each side

Type (0, 0), (2, 0), (4, 0), (4, 2), (4, 4), (2, 4), (0, 4), (0, 2), (2, 2): the four corners of a square of side 4, the midpoint of each side, and the centre. The lab reports 4 hull vertices, 8 boundary points, and 6 from gift wrapping. The centre is the only point of the nine that is neither a vertex nor on the boundary.

Read the per-point table and the shape of the disagreement is immediate. The four corners are marked as vertices and appear in all three runs. The four midpoints are marked as being on an edge; the chain excludes all four; and gift wrapping includes (2, 0) and (4, 2) while excluding (2, 4) and (0, 2). Nothing geometric distinguishes the two pairs. The wrapping walk starts at the lexicographically smallest point and goes round one way, and the collinear ties resolve in the scan's favour on the first two sides and against it on the last two.

Theorem · Where the two sets coincide

The vertex set and the boundary set of a finite point set S are equal if and only if no point of S lies in the relative interior of a segment joining two other points of S that both lie on the hull boundary. In particular, if no three points of S are collinear the two sets are equal.

A vertex is always a boundary point, so only one inclusion is at issue. Suppose p is on the boundary but not a vertex. Then p lies in the hull of the others, and since it is on the boundary it lies on some hull edge; being in the hull of the others and on that edge, it lies in the relative interior of the segment between the edge's two endpoints, both of which are on the boundary.

Conversely, if p lies strictly between two boundary points u and v, then p is a convex combination of u and v and so is in the hull of the others, hence not a vertex — and it is on the boundary because the segment uv lies in the hull and its endpoints do not permit p to be interior. The collinearity condition is necessary rather than sufficient on its own, which is exactly the case the previous lesson's nine points illustrate: they contain collinear triples and the two sets still coincide, because those triples are interior.

□

The two shipped algorithms are pinned against each other, on purpose

The gift-wrapping routine this course runs is a boundary walk, not a vertex list, and its tie-break is the sort order rather than a geometric decision. That is a real property of the implementation and the lab labels it as one: the mode checks gift wrapping against the boundary oracle rather than against the vertex set, and asserts only that every point it returns is on the boundary. The disagreement with the chain is recorded rather than smoothed over, so an upstream change that altered either one would fail loudly instead of quietly changing what this page teaches.

This is a deliberate editorial choice and it is the right one for a course about degeneracy. Making the wrapping return all eight, or exactly four, would remove the most instructive input on the page. What matters is that the page never calls its six the hull's vertex count, and never calls the chain's four the boundary.

The hull that is a segment, and the hull that is a point

Push the degeneracy further. Five collinear points have a hull that is a segment: the chain returns the two ends, the boundary oracle returns all five, and gift wrapping returns all five. A single point, typed twice, has a hull that is that point; the deduplication reports one duplicate removed and the chain returns the one point. Both of those are in the preset list, and both are answers rather than errors.

The shipped monotone chain in the shared algorithm library returns an EMPTY hull for a single point, because the lower and upper chains are both that point and both are sliced away when they are concatenated. The hull of one point is that point, so that is a defect; the geometry kit works around it with its own predicate-parameterised chain, and the arithmetic checker pins the disagreement so that a fix upstream cannot land silently. It is recorded here because a reader who runs the library routine directly will see the empty answer and should know why.

Interactive

The convex hull, and the three answers a collinear point produces

Two algorithms and two predicates, refereed by the definition itself

Four, six and eight, on the same nine points

Switch the algorithm control between the chain and gift wrapping and watch the drawn polygon change while the point colours do not: the colours come from the definition and the polygon comes from whichever algorithm you asked for. The per-point table is where the two midpoints gift wrapping keeps and the two it drops are visible.

Worked example

Points, as x, y

Draw the hull found by

Decide each turn with

Points typed—

Duplicates removed—

Hull vertices, exactly—

Hull vertices, in doubles—

Gift wrapping returns—

On the boundary, by definition—

Pushes and pops—

Work: n·h against n log2 n—

Points are x, y separated by semicolons. Duplicates are removed first and counted, because both algorithms return a repeated point when handed one. The colour of each point is decided by the definition and not by either algorithm: a point is a vertex when some line through it has every other point strictly beyond it, and on the boundary when some line through it has every other point on one side.

Method

Handling a collinear boundary without excluding it

Decide which question you are asking before you compare two answers.

Deduplicate, and keep the count

Do it before anything else and report how many were removed. Both hull algorithms return a repeated point when handed one, so this is not tidying — it is a precondition, and the count belongs on the page next to the answer.

Decide between vertices and boundary points explicitly

Write down which one the consumer needs. A renderer wants vertices; a point-location structure may want the boundary. Two correct procedures answering different questions will disagree, and the disagreement is not evidence that either is broken.

Find out what your wrapping implementation does with ties

Ask it for the hull of a square with a midpoint on each side. If it returns six, its tie-break is decided by scan order and its output is a boundary walk. If it returns four or eight, it has made a deliberate choice. Whatever the answer, you now know it rather than assuming it.

Check against the definition rather than against a second algorithm

Two algorithms agreeing is weak evidence when they share a convention about collinear points, and no evidence at all when they share code. The separating-line test answers the question directly and cannot share a convention with anything, because it has no incremental step in which to hold one.

Three answers, and the question each one answers

Score 0 / 0

Choose the answer you can justify.

All nine points, and what each of the three runs says

The square is (0, 0), (4, 0), (4, 4), (0, 4); the midpoints are (2, 0), (4, 2), (2, 4), (0, 2); and (2, 2) is the centre.

point definition chain wrapping boundary oracle (0, 0) vertex yes yes yes (2, 0) on an edge no yes yes (4, 0) vertex yes yes yes (4, 2) on an edge no yes yes (4, 4) vertex yes yes yes (2, 4) on an edge no no yes (0, 4) vertex yes yes yes (0, 2) on an edge no no yes (2, 2) inside no no no totals 4 6 8 the wrapping walk, in order: (0, 0) -> (2, 0) -> (4, 0) -> (4, 2) -> (4, 4) -> (0, 4) -> back to (0, 0)

The walk is the explanation. Wrapping starts at (0, 0), the lexicographically smallest point, and looks for the point that turns furthest clockwise. Along the bottom edge, (2, 0) and (4, 0) are tied at determinant zero, and the scan's comparison keeps whichever it reached in a position it cannot improve on, which here is (2, 0). The same thing happens at (4, 2). On the way back along the top and down the left side the ties resolve the other way, so (2, 4) and (0, 2) are skipped.

Nothing geometric distinguishes those two pairs from the other two, and here is the argument that settles it. Reflecting the whole input in the line y = x maps this point set onto ITSELF — it swaps (2, 0) with (0, 2) and (4, 2) with (2, 4) and fixes the rest. So the reflection is a symmetry of the input, and any answer determined by the geometry alone would have to be carried onto itself by it. Reflecting the six points the wrapping returned gives (0, 0), (0, 2), (0, 4), (2, 4), (4, 4), (4, 0), which is a different set. The output is therefore not decided by the geometry, and the only other thing in the algorithm is the order the scan walks in.

For a faded rehearsal, predict the three counts for the same square with midpoints but WITHOUT the centre point — eight points instead of nine. The supplied first move is that the centre is neither a vertex nor a boundary point, so removing it cannot change any of the three sets. Say what the three counts become, then say what happens to the 18 pushes and 12 pops, which do change.

Common mistakes

Calling a disagreement about collinear points a bugThree procedures returning 4, 6 and 8 on the same input looks like two of them are broken, and none of them is. Before reaching for a fix, ask what each one was computing; on this input the answer is three different things, and the lab labels each column with which.

Perturbing the input to make the degeneracy go awayNudging a midpoint by one unit does make all three agree, and it also answers a question about a different point set. Real inputs are full of collinear points — grids, rectilinear layouts, anything snapped to a lattice — and a procedure that only works once you have jittered the data is a procedure that does not work.

Treating a repeated point as harmlessBoth algorithms return a duplicated point when handed one, so the answer is not a set. The lab deduplicates first and reports the count, and the reason the count is shown rather than hidden is that it changes what n means in every cost figure below it.

Check your understanding

✓

Finish when you can predict all three counts on a degenerate input and say, for each one, which question it answers.

You should be able to state the vertex and boundary definitions and the condition under which they coincide, explain why a collinear tie-break makes gift wrapping's output implementation-defined, and say what deduplication changes and why its count is published.

Note: A hull is rarely the end of a computation; it is what makes the next one cheap. “The Two Furthest Points” uses it that way, walking the hull once to find the diameter of the whole set and then checking that answer against every pair of input points.