What a junction can save

The point nearest in total to three corners found the shortest road network joining three towns: a single junction from which every side of the triangle is seen at 120°. It ended with the general question. For more towns, the shortest network may need several junctions, each a point where three roads meet at 120°, and that essay stated the conjecture that bounds how much they can help: no set of towns in the plane has a shortest network shorter than $\sqrt3/2$ of its shortest spanning tree, the best network that uses only the towns themselves as junctions. The equilateral triangle sits exactly at the bound.

That essay drew the square’s network from its known shape and said plainly that nothing in it computed a shortest network for a larger set. This essay does compute them — exactly, by trying every way the junctions can be arranged — for sets of up to seven towns, measures how much junctions save on random sets and on sets chosen to make them save as much as possible, and finds the conjectured bound holding everywhere it can be tested and attained by more than the triangle.

The two networks in the figure differ by 6.3%, and the junctions that achieve it are where the spanning tree had two roads meeting at a town at an angle well under 120°. A spanning tree never bends a road except at a town; a network with junctions can split a road in mid-country and send the two halves off at the angle that balances them. Where the towns already sit at wide angles, there is nothing to gain, and five of the seven towns here are joined in the shortest network exactly as in the spanning tree.

How a shortest network is computed #

The two kinds of network are very different to compute. The shortest spanning tree is found greedily: repeatedly add the shortest road joining a town already connected to one not yet connected. The tree inside the triangulation showed that every road it uses is an edge of the Delaunay triangulation, so the whole computation takes about as long as sorting the distances, and each user pays for its own last link found that even dividing its cost fairly among the towns has a one-line answer. The shortest network with junctions has no such shortcut. Its junctions are new points, not towns, and a choice must be made of how many there are and what each one joins.

The method used for every network in this essay has two layers. The outer layer lists the patterns. A shortest network on $n$ towns needs at most $n - 2$ junctions, each meeting three roads; a pattern in which every one of the $n - 2$ junctions is present and every town is the end of exactly one road is called full, and every other pattern arises from a full one by letting some roads shrink to nothing, so that a junction slides onto a town or onto another junction. Listing the full patterns therefore lists everything. For four towns there are three: the towns are paired off two and two, and each pair shares a junction.

The inner layer optimises one pattern. With the pattern fixed, the total length is a convex function of the junctions’ positions — a sum of distances, each of which is convex — so it has one minimum and no false ones, and any procedure that keeps decreasing the length finds it. That is the property a line under every point identified as the useful content of convexity: at any point that is not the minimum there is a direction that goes down, so a procedure that only ever goes down cannot get stuck. The one used here moves each junction in turn to the Fermat point of its three neighbours, the point the previous essay constructed, and repeats until nothing improves. It has the shape of the rule in every site in the middle of its own cell, which moves each point to the centre of its own region and redraws, and it converges for the reason the landscape nobody is looking at gave for moves that settle: there is one number, here the total length, that every move lowers and that cannot fall for ever. When the best place for a junction is on top of a town, the iteration notices it and keeps the junction there; that is how the degenerate patterns, with fewer real junctions, are reached.

For the rectangle, the pattern that pairs each town with its neighbour across a short side wins clearly. The pattern pairing across the long sides is longer than the spanning tree, and the one pairing diagonal partners collapses both junctions into the centre and becomes the two diagonals. Which pattern wins depends on the shape — stretch the rectangle the other way and the long sides become short — and nothing short of optimising each says so in general.

Patterns beyond counting #

The previous essay counted the full patterns: $(2n - 5)!! = 1 \cdot 3 \cdot 5 \cdots (2n-5)$ for $n$ towns.

Seven towns need 945 optimisations, which is the hero figure, and each takes a few hundred rounds of Fermat-point moves. Ten towns would need two million, and fourteen more than three hundred billion. The exhaustive method stops being usable somewhere around eight or nine towns, and it was never the method anyone uses for real instances. Michael Garey, Ronald Graham and David Johnson proved in 1977 that finding the shortest network is NP-hard, so no method is expected to be fast on every set, but the programs that solve sets of thousands of towns — the GeoSteiner code of David Warme, Pawel Winter and Martin Zachariasen is the standard one — do it by proving, from the geometry, that almost every pattern cannot contain a shortest network, and optimising only the few that survive. A junction must see each of its roads at 120°, so a candidate piece of network whose junction would fall outside a certain lens between two towns is impossible before it is optimised, and pruning by such tests removes nearly all of the $(2n-5)!!$.

There is a physical computer for shortest networks, and it shows why the patterns matter. The least wall for equal rooms described soap films meeting three at a time at 120°; pins between two glass plates, dipped in soap solution, are joined by a film that is a network with 120° junctions. But a film only lowers its length until no small change lowers it further. It finds the best network within one pattern, and which pattern it lands in depends on how the plates were lifted from the solution. Dipped repeatedly, the same pins give different networks of different lengths. The soap does the inner layer of the computation perfectly and the outer layer not at all, which is exactly the part that makes the problem hard.

What junctions save on random towns #

With exact networks available for up to seven towns, the ratio of shortest network to shortest spanning tree can be measured on many sets.

The typical saving is small. On random triangles the average ratio is 0.980, a 2% saving; on random sets of four to seven towns it is 0.970 to 0.973. Many sets save nothing at all: whenever every angle at which two spanning-tree roads meet at a town is at least 120°, no junction can help, and the ratio is exactly 1. The smallest ratio among all 1,304 sets is 0.8758, a triangle close to equilateral, and no random set comes within a percentage point of $\sqrt3/2 \approx 0.8660$.

The reason the saving is usually small is visible in the hero figure. A junction can only help where two roads of the spanning tree meet at a town at an angle under 120°, and the saving there depends on how far under: two roads meeting at 90° can be shortened by a junction by only a few per cent of their length, and only roads meeting at sharp angles give much. In a random set, the spanning tree tends to join each town to its nearest neighbours, which lie in scattered directions, and sharp angles are the exception. The largest savings need three towns close to an equilateral triangle with nothing else nearby, and a random set rarely contains one.

That is reassuring and nearly useless as evidence for the conjecture. A bound that random sets never approach is a bound random sets cannot test: the dangerous sets, if there are any, are special, and a random search finds special configurations with probability zero. Small cases lie in both directions here — the ratios that random sets produce say almost nothing about the worst ratio, which is what the conjecture is about.

Searching for the worst set #

To test the bound the search has to aim at it. Wandering searches of this kind can be surprisingly strong — a walk that beats trying everything showed a random walk over assignments outperforming exhaustive search for satisfiability — but they guarantee nothing about the global minimum, and a search that stops is evidence only about where it looked. The procedure in the next figure starts from a random set, moves one town a small random distance, keeps the move if the ratio falls, and repeats, shrinking the moves as it goes.

Each run descends quickly from somewhere above 0.95 and then flattens, and each flattens at the same place: 0.8663 for four towns, 0.8686 for five, 0.8685 for six, with the dashed line at 0.8660 beneath all three. The final sets show what the search found. Every one has squeezed its towns into the shape of an equilateral triangle, with the surplus towns crowded onto its corners or onto each other — towns that coincide add nothing to either network, so a set of four towns, two of them in the same place, is an equilateral triangle in disguise and has its ratio. The search, given the freedom to place towns anywhere, rediscovered the triangle and found nothing better.

A local search is weak evidence about a global minimum, and the conjecture has been tested far more thoroughly than this, by searches over thousands of configurations and by exact case analysis. The conjecture has been proved for small numbers of towns, each by its own argument: for four towns by Henry Pollak in 1978, for five by Ding-Zhu Du, Yang Yao and Frank Hwang in 1985, and for six by Hyam Rubinstein and Jia Weng in 1997. Each proof is a case analysis over the patterns, and the cases multiply as the patterns do.

Sets that attain the bound #

The search reached the bound only by collapsing towns together. The lattice sets in the last figure reach it without collapsing anything.

The hexagon with its centre is seven towns, each at distance 1 from its neighbours, so its spanning tree is six roads of length 1. Its shortest network divides the hexagon into its six equilateral triangles and puts a junction at the centre of every second one — three junctions, each joining two corners of the hexagon and the centre, for a total of $3\sqrt3 \approx 5.196$. The ratio is $3\sqrt3/6 = \sqrt3/2$ exactly. It is three copies of the equilateral triangle’s network sharing a common corner, and the saving of each copy survives the sharing.

Not every lattice set does so well. Two triangles sharing a side give 0.8819: the shared side is in both triangles, and a network cannot use it twice. The triangle of six towns gives 0.8928. What the hexagon has and these lack is that its three served triangles meet only at corners, so each can be given its own junction without any road being wanted twice. That suggests building larger sets the same way, from equilateral triangles joined at corners, and such sets are the natural candidates for attaining the bound with many towns; the two drawn here are the ones computed exactly. Either way, the bound is attained by more than the single triangle, and every set that attains it is made of the triangle that first achieved it.

A proof that was accepted and then was not #

In 1990 Ding-Zhu Du and Frank Hwang published a proof of the full conjecture, for every number of towns. Its strategy was to reduce the question to a minimax problem over a family of functions and to show that the minimum occurs at configurations built from equilateral triangles, where the ratio is known. The proof was celebrated, entered textbooks and surveys, and was cited as a theorem for two decades.

In 2012 Alexander Ivanov and Alexei Tuzhilin showed that a step in the argument does not hold as stated: a lemma about where the minimax is attained is used under conditions it does not cover, and the gap could not be closed by the methods of the paper. The conjecture is now regarded as open again. What remains proved for every number of towns is weaker. Fan Chung and Ronald Graham showed in 1985 that the ratio is always at least 0.824, so junctions can never save more than about 17.6%; the conjecture says 13.4%. The distance between those two numbers is everything that is not known.

It is not the first accepted proof in combinatorial geometry to come apart. Alfred Kempe’s proof of the four-colour theorem stood from 1879 until Percy Heawood found the flaw in 1890, and five colours and a chain showed the exact step where Kempe’s argument fails and why the same argument still proves five. In both cases the gap was in a single step of a case analysis whose other steps were sound, and in both cases the statement survived the loss of its proof: the four-colour theorem was eventually proved another way, and the Steiner ratio conjecture is still waiting.

There is a lesson in the episode about the kind of claim at stake. The figures in this essay could have been read as corroborating a theorem, and for two decades that is how computations like them were read. They were the same computations before 2012 and after; what changed was the status of the argument they were measured against. A bound that every computation confirms, and that is attained by a whole family of sets, is about as well supported as a mathematical statement can be without a proof — and that is exactly the position of this one.

Still open: the ratio in the plane and beyond #

Whether every set of towns in the plane has a shortest network at least $\sqrt3/2$ times its shortest spanning tree is not known. It is proved for up to six towns and confirmed by every computation; the general proof that stood from 1990 to 2012 has a gap that has not been repaired.

In other settings even the conjectured value is unsettled. With roads restricted to north–south and east–west directions, the corresponding ratio is known: Frank Hwang proved in 1976 that it is exactly $2/3$. In three-dimensional space junctions still meet three roads at 120°, and a regular tetrahedron’s four corners give a ratio of about 0.813, below the plane’s $\sqrt3/2$ — but the tetrahedron is not the worst case. Warren Smith and J. MacGregor Smith showed in 1995 that long helical arrangements of points do better still, and conjectured a value near 0.784 for the worst case in space. No proof is in sight, and computing shortest networks in three dimensions is harder again, since the geometric pruning that makes the planar problem tractable for thousands of towns has no comparably strong counterpart in space.

The triangle is the worst case everywhere it has been looked for #

The Fermat point solved three towns with a construction. For more towns the shortest network is a search over a superexponential number of patterns, each solved by repeated Fermat constructions, and the search has been carried out here exactly for up to seven towns. What it measured is that junctions save a few per cent on typical sets and never more than $1 - \sqrt3/2 \approx 13.4\%$ on any set found, by random draws or by a search aimed at the bound; that the bound is attained, by the triangle and by every arrangement of triangles meeting at corners; and that the statement that it holds always, once a theorem, is again a conjecture.