The shortest wall that stops every line

Somewhere under a square field runs a straight buried cable. Nobody knows its position or its direction. The only thing known is that it passes through the field, and the only way to find it is to dig. How short can a trench be that is certain to meet it?

The trench can be any finite collection of straight or curved cuts, and it need not be connected. The object sought is what mathematicians call an opaque set, because a set that meets every line through a region blocks every straight line of sight across it. Stefan Mazurkiewicz asked about such sets in 1916, and the square has resisted ever since. The shortest wall known has length 2.63896. The best proof that nothing is shorter gets just past 2. That gap of about a third has stayed essentially where it is, on an object as simple as a unit square.

The first answers are easy to find and get better quickly. Three of the four sides of the square will do. A line meeting the square enters and leaves through its boundary, so it crosses the perimeter twice, counting corners suitably, and at most one crossing can use the missing side. That costs 3. The two diagonals cost $2\sqrt 2 = 2.828$: they meet every line through the square because any line that misses both diagonals leaves all four corners on one side. The tree joining all four corners by the shortest possible network, a Steiner tree of the kind studied in what a junction can save, costs $1 + \sqrt 3 = 2.732$, and that is the shortest connected wall built from the corners. And it turns out that the wall can be improved by breaking it, which nobody’s intuition about barriers suggests.

A proof that the wall is at least 2 #

The lower bound uses the theorem from a length counted by the lines that cross it. Crofton’s formula measures a curve by counting how many lines cross it, using the natural measure on the set of lines: a line is given by its direction $\theta$ and its distance $p$ from a fixed point, and a set of lines is measured by integrating $dp\,d\theta$. Under that measure, which does not change when the plane is moved, the formula reads

$$\int n(\text{line})\;dp\,d\theta = 2L,$$

where $n$ is the number of times a line crosses a curve of total length $L$. It holds for any union of segments, joined or not. It is the identity behind Buffon’s needle and it is the same one that the Favard length of a dust used. It treats the length round an ellipse, which has no formula, exactly as it treats a segment.

Apply the formula twice. The boundary of a unit square has length 4, and a line through a convex region crosses its boundary twice, so $2 \times (\text{measure of lines through the square}) = 2 \times 4$, and the lines through the square have measure 4. Now take any wall. Every one of those lines must cross it at least once, so the integral on the left is at least 4. Therefore $2L \ge 4$, and $L \ge 2$.

So half the perimeter is a lower bound for any convex region, and the argument is two lines long. Nothing better than this bound was known in general until the twenty-first century, and the improvements are tiny. Adrian Dumitrescu and Minghui Jiang proved in 2014, for walls lying inside the square, a bound of about $2.00002$. It took a substantial paper to raise the second decimal place of nothing.

What the bound is really counting #

The formula says more than the inequality. A wall of length 2 would be a wall that stops every line exactly once. It would have no waste at all. Every other wall has length exactly twice its mean number of crossings. So the length above 2 is a precise measure of how often lines are stopped more than once.

The figure integrates over all lines through the square. For three sides, half of all lines are stopped exactly once and half are stopped twice, for a mean of 1.5 and a length of 3. Two diagonals stop 58.6% once and 41.4% twice, mean $\sqrt 2$. The Steiner tree stops 68.3% once, 26.8% twice and 4.9% three times, a mean of 1.366. The two-piece wall stops 68.1% once and 31.9% twice, with no line stopped three times, for a mean of 1.3194, which is half of 2.63896. In every case the mean agrees with half the length to the accuracy of the integration, which here is a check on the Crofton identity itself.

This changes the question. Instead of what is the shortest wall, it becomes how nearly can a set of segments manage to stop each line only once. And it is obvious why that is hard. A wall with a corner in it is met twice by lines that clip the corner, just as a staircase pays more than a diagonal because lines cross it more often, and a wall that does not close up leaves lines escaping. The two-piece wall has an unusual profile: it gives up some of the once-stopped lines of the Steiner tree to get rid of the triply stopped ones entirely. It wins because the triple crossings are very expensive.

Checking a wall #

Confirming that a proposed wall really does stop every line needs a procedure, since there are infinitely many lines to check. It is a matter of shadows.

Fix a direction. All the lines in that direction form a parallel family, labelled by where they cross a perpendicular axis. Project the square onto that axis, and its shadow is an interval: those are the lines in this direction that meet the square. Project each segment of the wall onto the same axis. A line in this family misses the wall exactly when its label lies in no segment’s shadow. So the wall is opaque in that direction exactly when the segments’ shadows cover the square’s shadow.

All the shadows are piecewise linear functions of the direction, with changes in behaviour only where a segment’s end lines up with another’s. So it is possible to prove a wall opaque by checking finitely many ranges of directions. The figures use a simpler test: a sweep through 1,440 directions, each one checked exactly. That is a strong test rather than a proof, but for a wall with a small number of segments and rational or quadratic coordinates each design’s opacity can also be proved by hand, and the designs here have long been established.

The figure explains the waste too. Where the strips overlap, two segments are stopping the same line. A wall of length 2 would have strips that fit end to end in every direction at once, with no overlap. There is no such arrangement of finitely many segments, and that is really the content of the unsolved problem: shadows of segments cannot tile the shadow of a square in every direction simultaneously, and nobody knows how much overlap that forces.

Why two pieces #

The surprise is the winning design. Begin with the three corners $(0, 0)$, $(1, 0)$ and $(0, 1)$, and join them by their Steiner tree: three segments meeting at 120° at the point nearest in total to the three corners, which lies on the diagonal of the square through the origin, length $(\sqrt 2 + \sqrt 6)/2 = 1.93185$. Any line meeting the triangle of those three corners must meet that tree, since the tree spans its corners and a line that misses the tree leaves all three corners on one side. So the tree already deals with every line through that half of the square.

What is left is lines that meet the square and miss the triangle. Those are lines that cut off the fourth corner $(1, 1)$ without reaching the diagonal from $(1, 0)$ to $(0, 1)$, and they have a tidy measure: lines through the square have measure 4, lines through the triangle have measure equal to its perimeter $2 + \sqrt 2$, and so the escaping lines have measure $2 - \sqrt 2 = 0.5858$. This is what the curve starts from. To stop them, it is enough to run a straight stub from the fourth corner toward the centre, and it has to reach exactly as far as the diagonal, where the other half of the square begins. The stub costs $\sqrt 2/2$, and the total length is

$$\frac{\sqrt 2 + \sqrt 6}{2} + \frac{\sqrt 2}{2} = \sqrt 2 + \frac{\sqrt 6}{2} = 2.63896.$$

It does not need to go further, since a line that crosses the diagonal is already stopped by the tree. And it must not stop short. The curve in the figure falls gradually and reaches nought exactly there. The tip of the stub ends at $(0.5, 0.5)$ and the tree’s nearest point is its junction at about $(0.211, 0.211)$, leaving a gap of 0.41 between the two pieces. No line can pass through that gap and escape, since a line through the gap is blocked somewhere else. Connecting the pieces across the gap would be pure waste.

The same structure explains the failure of intuition. A wall sounds like something that must be continuous, because a physical barrier stops things that go round it. But straight lines cannot go round anything. For a straight line, being blocked is a question about what lies on it, and a break in a wall can be safe if everything that passes through the break is blocked further along. What matters is the shadows of the wall in each direction, and those shadows do not care whether the wall is connected.

What a blind search finds #

A natural sanity check is to run a search with no knowledge of the construction. Start from random segments, nudge their endpoints at random, keep any change that shortens the wall without letting more lines through, and see what comes out.

With two segments the search finds the two diagonals exactly, at length 2.8284 and no leak: that is the shortest two-segment wall anyone has found, and the search finds it from random starts. With three it finds nothing better, ending at 2.8296, a slightly bent copy. With four and five it reaches 2.697 and 2.687, with tiny leaks that the penalty has been unable to remove. It does not find 2.6390 in the time available, and it comes close enough to suggest what it is doing, which is approximating a tree with a stub, with slightly misplaced junctions.

The search is an honest test of how hard the landscape is. Short walls lie at sharp corners of the constraint: any small movement of a segment opens a leak, and a local search has to move several endpoints at once to keep things sealed. It shows no wall below 2.6390, and it does not show there isn’t one. Bernd Kawohl showed by a variational argument in the late 1990s that within certain restricted classes of walls, with a limited number of components and a specific structure, the two-piece wall is optimal. Beyond those classes nothing is known. There is no proof that a wall in many small pieces cannot beat it.

Other shapes, same problem #

The gap is a feature of the problem and not of the square, and it depends on the shape in an interesting way.

For the equilateral triangle of side 1, half the perimeter is 1.5 and the Steiner tree on its corners is $\sqrt 3 = 1.732$, and no improvement by splitting has been found. For the hexagon the Steiner tree is the perimeter less one side, 5, against the bound 3. The disc is the most instructive. Half its perimeter is $\pi$, and the best curve in one piece is an arc of half the circle extended by two tangents of length 1 at its ends, of total length $\pi + 2 = 5.1416$. This was proved to be the shortest connected opaque curve, because a connected curve blocks all lines meeting its convex hull. So its hull must contain the disc, and the problem becomes a neat optimisation. Splitting does better there too. Vance Faber and Jan Mycielski, in 1986, gave a design of total length 4.7998 in two pieces. It is the shortest wall known for the disc, and its ratio to the bound is 1.528, which is greater than the square’s 1.319 and much greater than the triangle’s 1.155.

So the rounder the shape, the worse the bound looks. Dumitrescu, Jiang and János Pach showed in 2014 that this cannot go arbitrarily badly. A wall within a factor of about 1.58 of the half-perimeter bound can be built for any convex polygon by a method that computes one in polynomial time. How close to 1 one can get for general shapes, or even for the square, remains unclear, and it would be remarkable if half the perimeter were the truth anywhere except for a line segment, the degenerate shape for which it is exact.

Lost in a forest, and other relatives #

The problem has several cousins, all with the same difficulty of escaping through their continuous freedom. Richard Bellman asked in 1956 for the shortest path that guarantees escape from a forest of known shape, starting at an unknown position, heading in an unknown direction. A closely related problem, asked by Leo Moser, seeks the smallest shape that can cover every curve of length 1 after moving it, and it is also open, with bounds that have barely moved. Henri Lebesgue’s universal cover asks for the smallest shape that covers every set of diameter 1. These all have one thing in common: a family of infinitely many objects must be dealt with by one finite one, and the easy averaging bound leaves a substantial gap that has resisted decades of work.

The opaque square has an additional feature that sets it apart, which is that the competing walls can have infinitely many pieces. Mazurkiewicz’s original paper already observed that an opaque set need be nothing like a curve: a set with no connected piece larger than a point can still meet every line. And a set of finite length can have shadows that nearly vanish in almost every direction. This is the phenomenon a dust that almost every line misses studies from the other side, and it is why an unconditional lower bound beyond the simple one is difficult: the proof must rule out sets that behave like Besicovitch’s constructions, whose length and shadows are related in unintuitive ways.

What these numbers leave undecided #

Four separate kinds of claim are in play in this essay, and they have different standing. The lengths of the designs are exact, and each was checked to agree with its closed form. Opacity of the designs was tested by a sweep over 1,440 directions at exact shadows; these walls are also known to be opaque by a direct argument. The Crofton means come from numerical integration on a grid of 720 directions and 2,000 offsets per direction, and their agreement with half the length is a check, not an independent derivation.

The search finds nothing and proves nothing, since it is a local method with a penalty rather than a global one, and a wall in many pieces is outside what it tried. The disc’s 4.7998 is quoted from Faber and Mycielski and was not recomputed here; a brief numerical search over the obvious family of arc, tangents and an added segment kept returning to the one-piece $\pi + 2$, and that says the design is delicate, not that it is wrong. The history of the lower bound, including 2.00002 and its restriction to interior walls, is cited and not reproved.

Still open: anything above 2.00002 #

What is the shortest wall for the unit square? The answer lies between about 2.00002 and 2.63896, and it is not known whether either is close to correct. There is not even a consensus among those who have worked on it, although the construction has held for decades, as to whether the upper value is optimal. It is not known whether an optimal wall exists in the class of finitely many segments, whether the shortest wall could need infinitely many pieces, or whether the infimum is attained.

Part of the difficulty is that the natural proof tool is an average, and an average knows nothing about the arrangement of the overlaps. Improving the bound means showing that overlap is unavoidable in a quantitative way: that because a wall of low length stops lines nearly once each, its shadows would have to fit together nearly perfectly in every direction, and that this rigidity is impossible. Whichever route succeeds would presumably apply to every convex shape.

A question about shadows #

A set stops every line through a square exactly when its shadow covers the square’s shadow in every direction, and by Crofton’s formula its length is twice the average number of times a line is stopped. So any wall has length at least 2, and the excess is overlap. The best wall known, 2.63896 long, is a Steiner tree on three corners with a stub that stops at the diagonal. Its two pieces do not touch, because to a straight line there is no such thing as going round.

Crofton’s formula turned a length into a count and gave a two-line proof of a bound that has barely been improved in a century. The formula is exact, and the gap between it and the best wall measures only what an average cannot see: how the overlaps have to be arranged.