Three points, however many there are

The four rungs below this one are about a curve and a chord. Convexity defined by chords, restated by supporting lines, described by its family of tangents, and what is lost when the chord dips — four essays about one function at a time.

A convex set is the same object seen from underneath: the region above a convex function’s graph is convex, and the questions asked about sets are the same questions with the roles of the axes forgotten. But they come out differently, and the difference is the whole of this rung. A question about one function has an answer that is a function. A question about convex sets nearly always has an answer that is a small whole number, and the number is the dimension plus one.

A mixture of three #

A point of the convex hull of a set is by definition a weighted average of points of the set — some finite number of them, with non-negative weights adding to one. Nothing in that definition bounds how many.

Carathéodory’s theorem does: in the plane, three suffice. In $d$ dimensions the number is $d + 1$, and it does not depend in any way on how many points there were.

It is worth being clear about what that sentence claims and what it does not. It does not say that three particular points work for every target — the three change as the target moves, and the figure above uses a different triple for each of its four. It says that for each target, somewhere among the triples, one contains it. Finding which is a search; knowing that the search terminates at three is the theorem.

The proof is a squeeze, and it is short enough to give. Suppose a point is a mixture of four points of the plane. Four points in the plane satisfy a linear dependence — four vectors in a three-dimensional space of coordinates-and-weights cannot be independent — so there are numbers, not all zero, adding to zero, with the corresponding weighted sum of the points equal to zero. Add a multiple of that dependence to the mixture. The point does not move; the weights change; and by choosing the multiple to be the first one that drives some weight to zero, one of the four points drops out. Repeat until three are left.

That argument is worth reading twice, because the same dependence is about to do a second job.

Four points, split #

Take the dependence itself, before it is used to eliminate anything. Separate its terms by sign: the points whose coefficients are positive on one side, the points whose coefficients are negative on the other. Both sides are non-empty, because the coefficients add to zero and are not all zero.

Now normalise each side by the total weight on it. The two sides produce the same point — that is exactly what the dependence says — and each expresses it as a weighted average of the points on its own side. So the two hulls meet.

Radon’s theorem: any $d + 2$ points in $d$ dimensions split into two groups whose hulls intersect.

The number is one larger than Carathéodory’s for a reason the proof makes plain: Carathéodory needs the dependence to exist so that it can eliminate, and Radon needs the same dependence so that it can divide. Both are consuming the fact that $d + 2$ vectors in the $d + 1$ coordinates a point-and-its-weight has must be linearly dependent, which is a fact about a matrix having more columns than rows and nothing more. In the plane that is four points, and the two shapes it can take are both visible in the drawing: two segments crossing, or a point inside a triangle.

The theorem is trivial to state and does not look useful. It is the engine of the next one, and it is a good example of a result whose importance is entirely in what it proves rather than in what it says. Nobody wants to split four points; everybody wants the consequence.

The split is also not unique, and the figure’s is the one the dependence happens to produce. Four points in general position admit exactly one split into two non-empty groups with intersecting hulls, but four points with three of them collinear admit more, and the degenerate cases are skipped by the sweep above rather than handled — 400 quadruples were drawn at random and the ones whose dependence collapsed were passed over, which the figure reports rather than conceals.

Every three, and therefore all #

Here is the question a convexity theorem is usually asked in practice. A family of convex sets is given — constraints on a design, half-planes in a linear programme, discs a transmitter can reach — and one wants to know whether they have a point in common. Checking all of them at once is the whole problem. Checking a few at a time is cheap.

Helly’s theorem says that in the plane, checking three at a time is enough. If every three sets of a finite convex family have a common point, all of them do.

The proof is Radon’s theorem and an induction, and it is worth seeing because it explains where the three comes from. Suppose the theorem holds for families of $n$ sets and take a family of $n + 1$. Leaving out one set at a time gives $n + 1$ subfamilies of size $n$, each of which — by the inductive hypothesis — has a common point. That produces $n + 1$ points, one per omitted set, each lying in every set except possibly the one omitted.

Take four of those points. Radon splits them into two groups whose hulls share a point. That shared point lies in every set of the family, and the argument for that is the pleasant part: a set is omitted by at most one of the four, so it contains at least three of them, so it contains one whole group’s worth and — being convex — contains the hull of that group, and hence the shared point.

Four points is what Radon needs, and four points is $d + 2$. The three in Helly’s hypothesis is $d + 1$, and it is there because dropping one set at a time from a family of $d + 2$ leaves families of $d + 1$. The two numbers are the same number, arrived at from different sides.

Two is not enough #

A theorem that says three at a time invites the question of whether two would do, and the answer is a picture.

The example generalises exactly: in $d$ dimensions, the far sides of the $d + 1$ faces of a simplex meet $d$ at a time and never all at once. So the theorem’s number cannot be lowered anywhere, and the “one more than the dimension” is not an artefact of a convenient proof.

It is worth saying what the counterexample is not. The three half-planes are convex, closed, and perfectly ordinary; nothing about them is pathological. What fails is only the counting, and it fails at exactly one below the theorem’s threshold. That is the signature of a sharp result, and it is why these three theorems are quoted with their numbers rather than as qualitative statements.

A point that no half-plane can isolate #

Helly’s theorem earns its keep through corollaries that mention neither families nor intersections, and the cleanest of them is worth stating in full.

Given any finite set of points in the plane, there is a point — not necessarily one of them — such that every half-plane containing it contains at least a third of the set. Such a point is called a centrepoint, and its existence is not obvious: it says that no matter how the points are arranged, no straight cut can push the point into a thin minority.

The proof is Helly applied to a cleverly chosen family. For each open half-plane holding more than two thirds of the points, take the convex hull of the points it holds. These hulls are convex, and any three of them have a common point, because three half-planes each missing fewer than a third of the points cannot between them miss all of them — so some point of the set lies in all three, and therefore in all three hulls. Helly then supplies a point common to every hull in the family, and a point in every such hull is a centrepoint.

The three in the conclusion is the three in Helly’s hypothesis, which is the dimension plus one, and in $d$ dimensions the fraction is $1/(d + 1)$. So the guarantee weakens as the dimension grows, in exactly the way the theorem behind it does.

What makes this the right example to give is that the statement contains no convex sets at all. It is a fact about a scatter of points and a family of cuts, and the convexity is entirely in the proof. That pattern — a combinatorial conclusion whose only route is through a Helly-type intersection theorem — is most of what these theorems are for.

Where the counting is actually used #

The setting where Helly’s number is doing daily work is linear programming, and the restatement is exact.

A system of linear inequalities in $d$ variables describes an intersection of half-spaces, each of which is convex. If the system has no solution, Helly says that some subsystem of $d + 1$ inequalities already has none — because if every $d + 1$ of them were satisfiable, all of them would be.

That is a strong statement about certificates. An infeasible system of ten thousand constraints in two variables is infeasible for a reason involving three of them, and the three can be named. Anybody doubting the infeasibility can be handed those three and check them by hand, without repeating any of the work that found them. The dual of a linear programme supplies a certificate of the same kind by a different route, and the two are related: the dual’s witness is a combination of constraints, and Helly’s is a subset of them.

It is also the reason low-dimensional linear programming is fast in a way that has nothing to do with the number of constraints. An algorithm that only ever has to consider $d + 1$ constraints at a time can process the rest incrementally, and the running time comes out linear in the number of constraints with a constant that depends — badly, but only — on the dimension. The dimension-dependence that made these theorems useless in a thousand dimensions is the same dependence, seen in a running time instead of in a subfamily count.

Why the size of the family does not matter #

The most surprising feature of all three theorems is what is missing from them: the number of points, or of sets, appears nowhere in the conclusion.

That independence is what makes the theorems usable. A constraint family of ten thousand convex sets is checked three at a time; a mixture of a million points is rewritten with three; and the cost of the conclusion is set by the dimension one is working in and not by the size of the problem.

The dimension is therefore the quantity that hurts, and it hurts immediately. In three dimensions Helly needs every four; in ten dimensions every eleven, and the number of eleven-element subfamilies of a large family is enormous. These theorems are cheap in the plane, expensive in ten dimensions and useless in a thousand, which is the same trade every geometric method makes and is worth stating in a rung that otherwise reads as a free lunch.

Where else the same shape appears #

A statement of the form check every $k$ and the whole thing follows is a local-to-global result, and once the shape is recognised it is visible in several places on this site with quite different mechanisms behind it.

A bottleneck condition on every subset decides whether a matching exists, which is a local-to-global statement with $k$ unbounded — every subset must be checked — and is correspondingly harder to use than Helly.

Six people at a party is the opposite arrangement: no amount of local information forces the global conclusion, and what forces it is size. The Ramsey numbers measure how much size is needed, and they grow, whereas Helly’s three does not.

And the closest relative is the one that looks least similar. A convex region large enough must swallow a lattice point is also a statement about convex sets whose conclusion depends only on the dimension — through a constant, $2^d$, which does grow. That comparison is the useful one: Helly’s number is a count of sets and Minkowski’s is a volume, and the first is dimension-free while the second is exponentially dimension-dependent.

The one that is not like the others #

Three theorems, one mechanism, and it is worth separating them by what they are about, because the family resemblance hides a real difference.

Carathéodory is about a single set and says its hull is built out of small pieces of it. Radon is about a single finite set and says it can be divided. Helly is about a family of sets and says something about their intersection. The first two are constructive — each hands over the triple or the split it promises — and the third is not: Helly’s proof produces a point by applying Radon to points produced by an induction, and following the recursion for a family of a thousand sets is not a practical way to find the common point.

That is the usual state of affairs with an intersection theorem, and it is worth naming because it changes how the result is used. Helly is a guarantee, and the way to exploit a guarantee is to run a cheap procedure and know in advance that it will succeed, rather than to extract an answer from the proof. The linear-programming algorithms below do exactly that: they never build Helly’s point, they use the fact that it exists to justify only ever looking at three constraints at a time.

What the pictures cannot show #

Every figure here is planar, and the theorems are stated in the plane throughout. The general statements — $d + 1$, $d + 2$, and $d + 1$ again — are asserted with their proofs sketched and drawn nowhere, because a figure of the four-dimensional case would be a diagram of an argument rather than a picture of the objects.

The Helly figure works over a grid of sample points, so its shaded region is a set of samples rather than the exact intersection, and its counterexample says that no sampled point lies in all three rather than that no point does. The half-planes are simple enough that the two statements coincide, and the figure is honest about which it performed.

And the infinite case is untouched. Helly’s theorem for an infinite family needs the sets to be compact, or one of them to be, and the failure without that hypothesis is easy — nested half-planes marching off to infinity meet in every finite subfamily and nowhere at all. Nothing here draws it, and it is the hypothesis a reader is most likely to drop.

Where the ladder goes next #

Named here as debts. The fractional and colourful versions, where Helly’s hypothesis is weakened to most triples and the conclusion weakens correspondingly — the results are recent, they are what make the theorem useful in computational geometry, and they need their own rung. And Tverberg’s theorem, which is Radon with two parts replaced by $r$ parts and is the natural end of this particular line.

Sideways, the supporting line that turns a local fact global is the second rung, the function-shaped version of a convex set is its epigraph, and what happens when convexity is simply absent is the rung below.

What is worth carrying away #

When a property is defined by a condition on arbitrarily many objects, ask how few objects the condition really needs.

Membership of a convex hull is defined by mixtures of any size and is achieved by three. A common point is a condition on a whole family and is decided by triples. In both cases the definition’s unboundedness was an artefact of how it was written, and the true number is one more than the dimension.

The habit worth taking is to look for the linear dependence. All three theorems here come from the same source — that $d + 2$ points in $d$ dimensions cannot be affinely independent — and the whole subject is that single fact, applied to eliminate a term, to split a set, and then to induct.

The corollary is about reading a bound. A bound that does not mention the size of the input is usually the shadow of a dimension count, and finding the count is more useful than remembering the bound: it says immediately what the bound becomes in another setting, and it says which hypothesis to check when the bound appears to fail.