Lines that leave half on each side

One line that halves them both is the theorem this essay starts from, and its proof needs no cleverness. Fix a direction, slide a line in that direction until it cuts a shape in half, and turn the direction slowly through half a revolution. Whatever was on the left is now on the right, so any quantity that compared the two sides has reversed its sign, and somewhere along the way it was zero. That one observation halves two shapes with one cut, splits a necklace between thieves and, run one dimension up, finds two opposite places on the Earth with the same weather.

This essay runs the argument on the simplest possible input: a finite set of points. A shape has a halving line in every direction, and that is the end of the matter. A set of points has the same, but the lines worth counting are the ones that pass through two of the points and leave equally many on each side, and how many of those there can be turns out to be one of the hardest counting questions in the geometry of the plane.

What a halving line is #

Take an even number $n$ of points in the plane, no three on a line. A halving line is a line through two of the points with $(n - 2)/2$ of the others on each side. For ten points that means four on each side, and the figure at the top draws all thirteen of them for one arrangement.

The definition is a finite version of a bisection. Shift a halving line very slightly to one side and it passes through no point at all and has exactly five on each side; any line that splits ten points five and five can be turned until it hits one point on each side, and then it is a halving line. So the halving lines are the extreme positions of the lines that split the set evenly, and counting them counts how many essentially different even splits by a straight cut the set has.

The smallest case shows the whole range in miniature. Four points either form a convex quadrilateral or a triangle with one point inside. In the quadrilateral the halving lines — one point on each side — are the two diagonals, and the sides are not, since a side has both other points on the same side of it. In the triangle with a point inside, the three lines from the inner point to the corners are halving lines, each leaving one corner on either side, and the sides of the triangle again are not. So four points have two or three halving lines and nothing else, the convex arrangement giving the fewer and the nested one the more, which is the pattern every larger case repeats.

The figure’s arrangement was found by a search, and thirteen is the most any ten points can have. The search had to work for it: random arrangements of ten points give between five and eleven, with the low end most common.

Turning a direction through half a revolution #

The connection to the ham-sandwich argument is direct. Fix a direction and project the points onto the line at right angles to it; the projections come in some order, and a line in the fixed direction splits the set evenly exactly when it falls between the fifth and sixth projections. The figure draws the gap between those two, the middle two, as the direction turns.

Most of the time the gap is positive, and there is a band of even splits in that direction. When the middle two points pass each other — their projections coincide, and then reverse — the line through them in that direction has four points on each side. That is a halving line, and the gap there is zero. When instead a point from outside slides into the middle, replacing one of the pair, the gap changes but does not reach zero.

Over half a revolution every halving line is met exactly once, since a line has one direction modulo a half-turn. So the halving lines are the zeros of a quantity defined on a half-circle of directions, and their number is the number of times the middle pair trades places. The computation finds thirteen trades at thirteen distinct angles, matching the thirteen lines found by checking every pair of points directly.

Every point on an odd number of them #

The small numbers in the hero figure are 1, 3, 3, 3, 3, 5, 3, 1, 1, 3 — all odd — and that is not luck. The figure above checks it on two thousand random sets of twelve points, every point of every set: 21,647 points lie on one halving line, 1,741 on three, 449 on five, and so on up to one point on eleven. Not one lies on an even number.

The proof is the turning argument again, now centred on a single point, and it is a parity argument of the same kind as the sign of a permutation: what is counted is not how many changes happen but whether their number is odd. Put a line through a point $p$ and turn it about $p$ through half a revolution. The other $n - 1$ points, an odd number, are split between the two sides, so one side always has more. Each time the line passes another point, that point changes sides. The side with more changes from the one to the other exactly when the line passes through a point $q$ with the rest split evenly — that is, when $pq$ is a halving line. After half a turn the line is back where it started with its two sides exchanged, so the side with more has switched an odd number of times. The halving lines through $p$ are an odd number.

Two consequences follow at once. Every point lies on at least one halving line, so there are at least $n/2$ of them, since each line uses two points. And the total, counted through the points, is a sum of $n$ odd numbers, which is even, as it must be since each line is counted twice.

Two sets halved at once #

The discrete version of the ham-sandwich theorem follows from the same picture. Take two sets of points, say ten red and ten blue, all in general position. For each direction there is a band of lines splitting the red points evenly and a band splitting the blue; turn the direction through half a revolution and the order of the two bands, which is above the other, must reverse, because everything above is now below. Somewhere they overlap, and a line in the overlap, passing through none of the points, has five red and five blue on each side — a ham-sandwich cut for points.

That is the finite form of one line that halves them both, and it shows what the finite setting adds. For shapes, the bisecting line in a given direction is unique and moves continuously, so the turning argument meets a single crossing. For points, the even splits come in bands that jump as points pass one another, and the halving lines are where the bands narrow to nothing. The topology guarantees that the jumps cannot all be avoided; the combinatorics asks how many there are, and the question this essay is about is the second one.

The same distinction runs through the other theorems of this kind. Seven points split three ways proved that a partition with a common point must exist, and left open how many there are. Four equal quarters with two lines proved a division exists for any shape, where the number of such divisions depends on the shape. Each time, topology gives existence through a sign change, and counting the sign changes is a separate and usually harder problem. Halving lines are the cleanest case of it: the existence is the parity argument above, and the count is the k-set problem.

Random points have few #

The odd-degree figure carries a second measurement that is easy to miss. Of the 24,000 points, 21,647 — about nine in ten — lie on exactly one halving line, the least possible. Adding the degrees and halving gives the average number of halving lines in a random set of twelve points: about 7.6, against a minimum of six and a maximum of eighteen.

So a random set sits near the bottom of the range, and the reason is the one the convex case makes plain. A point on the outside of the set can be turned about and passes the halving position once; only a point deep inside, with others all around it, can pass it repeatedly. Points thrown into a square are mostly near the outside in the relevant sense: the layers of nested hulls are few, and most points lie on the outer two or three. The arrangements with many halving lines are built rather than found, with the points arranged in many nested layers so that most of them can be wound round, and that is why a search that starts from random arrangements has to work so hard to approach the maximum.

The fewest: points in convex position #

The lower bound is attained. If the points lie in convex position — around a loop, none inside the hull of the others — then the line through two of them leaves the points strung between them on the loop on one side and the rest on the other, and it halves the set exactly when the two are opposite, $n/2$ places apart. That gives $n/2$ halving lines, each point on exactly one, the least the parity allows.

Pushing a single point inside breaks this. The interior point can be turned about and pass the halving position more than once, and the count rises; in the figure it goes from six to seven, with the interior point on three halving lines. Every point inside the hull of others is a point that the turning argument can wind round, and the arrangements with many halving lines are the ones where the points are nested deeply inside one another, as the clustered middle of the hero figure is.

The most: the k-set problem #

The maximum is the hard direction. For small sets it is known exactly: 3 for four points, 6 for six, 9 for eight, 13 for ten, 18 for twelve, 22 for fourteen, 27 for sixteen, 33 and 38 for eighteen and twenty, values established by Bernardo Ábrego, Silvia Fernández-Merchant and their collaborators by combining computer search with lower-bound arguments, and extended by them to 27 points.

The search drawn here, which moves one point at a time and keeps any move that does not lose a halving line, matches the maximum up to ten points and then falls behind: 17 instead of 18 for twelve points, 20 instead of 22 for fourteen, 23 instead of 27 for sixteen. The best arrangements are special — highly structured, with points nested in layers — and a local search that improves one point at a time rarely finds them. That is the practical face of the problem: even the exact values for small $n$ needed more than search.

For large $n$ the question is how fast the maximum grows. The lower bound has a short history. Paul Erdős, László Lovász, A. Simmons and Ernst Straus showed in 1973 that $n$ points can have at least a constant times $n \log n$ halving lines, and Géza Tóth improved this in 2001 to $n e^{c\sqrt{\log n}}$ — more than $n$ times any power of the logarithm, but less than $n^{1 + \varepsilon}$ for every $\varepsilon$. The upper bound was $n^{3/2}$ from Lovász’s paper of 1971 until Tamal Dey proved in 1998 that it is at most a constant times $n^{4/3}$.

Between $n e^{c\sqrt{\log n}}$ and $n^{4/3}$ nothing has moved for a quarter of a century. The search figure shows why small cases cannot settle it: the values to twenty points sit on a gently rising curve that looks equally like either bound, and the asymptotic difference between them only shows at sizes far beyond any exhaustive search.

Where the four-thirds comes from #

Dey’s bound has a proof that connects back to an earlier essay in this collection, and it is worth sketching because it is a crossing count.

Draw every halving line as a segment between its two points, so that the halving lines become the edges of a graph drawn with straight lines on the points. Dey showed that these segments can be grouped into $n/2$ convex chains — each chain is the path a halving line traces as it is turned, pivoting from point to point, which is the turning argument once more — and that two convex chains cross each other only a bounded number of times. So the halving segments cross at most a constant times $n^2$ times in all.

Against that, the crossing lemma says that any drawing of a graph with $n$ vertices and $h$ edges, once $h$ is a few times larger than $n$, has at least a constant times $h^3/n^2$ crossings: a graph with too many edges cannot be drawn without crossing itself often. The halving graph has $h$ edges and at most about $n^2$ crossings, so $h^3/n^2$ is at most a constant times $n^2$, and $h$ is at most a constant times $n^{4/3}$.

So the upper bound is a collision between a topological fact — drawn graphs with many edges must cross — and the geometric fact that halving segments are arranged by the turning argument and cannot cross freely. The same pair of ideas gives the best known bound on the rectilinear crossing number of the complete graph, through a closely related count of the lines that leave at most $k$ points on one side, which is how the exact values of halving lines and of crossing numbers for small $n$ were found together.

What the computations rest on #

Every halving line in the figures is found by checking every pair of points against every other point, which is exact for points in general position; the count rejects any arrangement with three points on a line, so no count is spoiled by a tie. The odd-degree check runs on all 24,000 points of the random sample and on every arrangement the figures draw.

The search for many halving lines is a heuristic and its numbers are lower bounds on the maximum, set against the published maxima rather than offered in place of them. The turning figure computes the projections at 3,600 directions across the half-turn and identifies each halving line by the middle pair trading places; it agrees with the direct count on all thirteen lines.

Still open: the exponent #

How fast does the greatest number of halving lines of $n$ points grow? It is at least $n e^{c\sqrt{\log n}}$ and at most a constant times $n^{4/3}$, and the true order is not known even to the power of $n$. Both halves of the problem go back to László Lovász, who proved the $n^{3/2}$ bound for halving lines in 1971 and seven years later proved a colouring theorem by topology that founded the topological method behind every theorem here; neither line of work has produced a tight count. Most researchers expect the lower bound to be closer to the truth, so that the maximum is $n^{1 + o(1)}$, but no construction does better than Tóth’s, and no argument beats Dey’s.

The same question in three dimensions — planes through three of $n$ points with equal numbers on each side — has a gap that is wider still, between about $n^2 e^{c\sqrt{\log n}}$ and $n^{5/2}$. In every dimension the lower bound comes from constructions with points nested in layers, the upper bound from crossing arguments, and the turning argument behind the ham-sandwich theorem is the one tool that works in both directions.