A chain of tetrahedra saves more

What a junction can save compared two ways of joining towns by roads. The shortest network that may branch only at the towns themselves — the shortest spanning tree — is easy to find. Allowing junctions anywhere makes the network shorter, and in the plane, it is conjectured, never by more than the equilateral triangle’s 13.4%, the saving the point nearest in total to three corners makes by joining the three corners at a point that sees each side at 120°. The ratio of the two lengths, never below $\sqrt3/2 \approx 0.866$ in every computation so far, is called the Steiner ratio, and the plane’s version is still not proved.

That essay ended by pointing into space, where pipes and wires run in three dimensions and junctions still meet three branches at 120°. There the obvious candidate for the worst case is the regular tetrahedron, the three-dimensional equilateral triangle. This essay computes its ratio, the ratios of its relatives in four and five dimensions, and then a family of point sets that beats it: points spaced along a chain of regular tetrahedra glued face to face, which do worse for junctions the longer the chain grows.

Computing a shortest network in space #

A shortest network with junctions — a Steiner minimal tree — has the same structure in space as in the plane. Every junction joins exactly three branches meeting at 120°, since a junction where the angles were otherwise could be moved to shorten the network, and a network on $n$ points has at most $n - 2$ junctions. The pattern of which branches join which — the network’s topology — is the hard part. For $n$ points there are $(2n - 5)!!$ full patterns, each with $n - 2$ junctions: 1 for three points, 3 for four, 15 for five, 105 for six and 945 for seven.

For a fixed pattern the junctions’ positions can be found by an iteration Warren Smith published in 1992. Each junction is moved to the weighted average of its three neighbours, each neighbour weighted by one over its distance, and the step is repeated; the total length falls at every step, and the junctions settle where the three pulls balance, which is exactly where the branches meet at 120°. A pattern that is not really the best may settle with a junction pressed against one of the points, which is how networks with fewer junctions appear. Trying every pattern and keeping the shortest gives the shortest network; for up to seven points that is what every figure here does, and the shortest spanning tree is found the ordinary way, by repeatedly adding the shortest road that reaches a new point.

The method is the same in any number of dimensions. Only the distances change, which is what makes it possible to follow the regular tetrahedron’s relatives up through four and five dimensions.

The regular simplex, dimension by dimension #

The regular simplex in $d$ dimensions has $d + 1$ corners, every pair at the same distance: the equilateral triangle, the regular tetrahedron, and their analogues, one in each dimension, as six in four dimensions, and three forever after counted. Its shortest spanning tree is any path through the corners, $d$ edges of length one. Its shortest network with junctions is found by trying every pattern — 1, 3, 15 and 105 of them for two to five dimensions — and the ratio falls with every dimension: $0.8660$ in the plane, $0.81305$ in space, $0.7837$ in four dimensions and $0.7646$ in five.

For the tetrahedron the network is drawn on the left of the hero figure: two junctions on the segment joining the midpoints of two opposite edges, each joined to the two corners of its edge, and the four branches from them to the corners meeting the junction-to-junction segment at 120°. The two junctions do the work that one junction does in a triangle, and they do more of it, because in space the branches can come in from four directions at once.

The falling ratio has a simple cause. In more dimensions there is more room for the paths from different corners to share their length before splitting, and the regular simplex, symmetric in every direction, uses that room evenly. That suggests the regular simplex might be the worst case in every dimension, just as the triangle seems to be in the plane. It is not.

A chain of tetrahedra #

Glue regular tetrahedra face to face in a line, each new one sharing a face with the last, always turning the same way. The result is the Boerdijk–Coxeter helix, a twisted column whose corners lie on a helix, every four consecutive corners forming a regular tetrahedron. Take $n$ consecutive corners. Every point is at distance one from the three before it and the three after, so the shortest spanning tree has $n - 1$ edges of length one, and the shortest network can be computed with junctions joined in a path running up the column, each holding the next point in turn — the spine visible on the right of the hero figure.

Four points are the regular tetrahedron, at $0.81305$. Five points do slightly worse for junctions, $0.81547$, because the fifth point extends the chain in a way that the spanning tree can follow cheaply. From six points on the ratio falls with every point added: $0.8081$ at six, $0.7947$ at twelve, $0.7903$ at twenty, $0.7862$ at sixty. Plotted against $1/n$, the last values lie close to a straight line, and its continuation to an endless chain gives about $0.7841$.

That is the value Warren Smith and J. MacGregor Smith reached in 1995, with a more careful analysis of the infinite chain: about $0.78419$, which they conjectured to be the Steiner ratio of three-dimensional space. The tetrahedron is therefore not the worst case. A long chain of them is worse, by about three percentage points, and nothing worse than the chain has been found.

For up to seven points the computation checks that the chain’s spine is really the shortest pattern, not just a good one: every one of the 3, 15, 105 and 945 full patterns was optimised, and the best agrees with the spine to five decimal places. For longer chains, trying every pattern is out of reach — 2.0 × 10⁶ patterns at ten points, 10²⁰ at twenty — and the spine is taken on trust, as Smith and Smith took it.

Why a chain is worse than a single tetrahedron #

The chain wins by repetition. A single tetrahedron’s network has two junctions and five branches, and the four branches to the corners are longer than they would be if the corners had neighbours on the far side to share with. In the chain, almost every point is in the middle, with neighbours on both sides along the column, and its junction sits between the junctions of the points before and after it on a spine that runs the length of the column. Each point costs a short branch to the spine plus its share of the spine, and the spine is shorter than the unit edges the spanning tree has to use, because it runs straight up the column’s twisted centre while the spanning tree has to walk round the outside.

The bookkeeping can be done directly from the computed lengths. Twelve points along the chain have a spanning tree of length 11 and a network of length 8.742. Going from forty points to sixty adds 20 to the spanning tree and 15.68 to the network, so each point in the middle of a long chain costs 0.7842 of network for every 1 of spanning tree — the limiting ratio itself, read off as a marginal cost rather than extrapolated, and equal to the Smiths’ $0.78419$ to the four places the computation carries. Nothing about that figure depends on fitting a line; it is the cost of twenty more points in the middle of a chain long enough that its ends no longer matter. The middle of the chain is already at the limit; only the ends hold the average above it.

The ends of the chain are where the advantage is lost. The first and last few points have neighbours on one side only, and they cost more, as the lone tetrahedron does. With $n$ points the ends are a fixed cost spread over $n$, which is why the ratio approaches its limit like $1/n$ and why five points, nearly all ends, are worse than four.

The same reasoning points to why the plane behaves differently. Laid flat, the best repeating pattern is the triangular lattice, and what a junction can save found that its large pieces — a hexagon with its centre — do exactly as well as one triangle and no better: the plane’s worst case repeats without improving. Space has a repeating pattern, the chain, that improves on its own first piece, and that is the difference the hero figure shows.

What space takes away from the search #

In the plane the shortest network for thousands of towns can be computed exactly, and the reason is pruning. Most of the $(2n-5)!!$ patterns can be thrown out before any junction is placed, because a branch of a shortest network must lie inside regions defined by the towns near it. The tree inside the triangulation showed the simplest version of that idea for spanning trees: the shortest spanning tree uses only edges of the Delaunay triangulation, so only a few edges per town ever need considering. For networks with junctions the corresponding tests — lunes and wedges in which no other town may lie — are strong enough in the plane that the full search becomes a search over small pieces that are then glued together.

In space those tests are much weaker. A junction’s three branches lie in a plane, but that plane can be tilted any way, and the regions a branch must avoid are thinner relative to the space around them. The shortest spanning tree still lives inside the three-dimensional Delaunay structure — the containment argument works in any dimension, as one dimension up and the circles disappear found for the lifting map that builds it — but the networks with junctions do not prune nearly as well. Exact shortest networks in space are computed for tens of points, not thousands, and that is part of why the chain was found by reasoning rather than by a large search.

There is also a reason in geometry for why space is generous to junctions. In the plane a junction’s 120° is the only way three branches can balance; in space the three branches still balance at 120°, but the plane containing them can turn freely, so a network can twist from one junction to the next, as the chain’s spine does round the column. The twist is what lets the spine stay short while every point along a helix stays close to it.

Random points come nowhere near #

Random points tell a different story. Four, five or six points chosen uniformly in a cube have shortest networks about 5% shorter than their spanning trees on average, and among 750 random sets the least ratio is $0.846$ — far above the tetrahedron, let alone the chain. Most random sets have one or two points much closer to each other than to the rest, and a junction can do little for a point whose nearest neighbour is right beside it. In more dimensions random points become more evenly spread — in high dimension nearly every pair of random points is at almost the same distance, the concentration a sphere that is nearly all equator measured — so random sets drift towards the regular simplex as the dimension grows, but in three dimensions they are still far from it. The worst cases are the most evenly spread sets possible, and evenness is exactly what random points lack.

Searching does not find the chain either #

A natural way to look for bad sets is to start from a random one and improve it: move all the points a little, keep the move if the ratio falls, and shrink the moves when they keep failing. For four points the best of three searches climbs to $0.8142$, within a hair of the regular tetrahedron. The other two stall at $0.874$ and $0.859$. For five and six points every search stalls well above the chain’s values for those sizes, $0.8155$ and $0.8081$.

The landscape of point sets is rugged. Moving one point changes which pattern of junctions is best, and the ratio jumps from pattern to pattern, so a search that only goes downhill stops at the first arrangement from which every small move makes things worse. What a junction can save found the planar search drifting towards collapsed configurations, two towns on top of each other, which reach the planar bound in a degenerate way; in space the searches here did not even find the tetrahedron reliably. The chain was found by thinking about the problem, not by searching, and it is not the kind of shape a local search walks into.

What the computations do and do not establish #

Every network here is computed, not proved shortest. For up to seven points every pattern was tried, but each pattern’s junctions are found by an iteration that converges to the right positions without a certificate of how close it is; the agreement of independent patterns and the 120° angles at the settled junctions are the evidence. For longer chains only the spine was computed. The extrapolation to $0.7841$ rests on fitting a line in $1/n$ through the values at forty and sixty points, and it matches the Smiths’ $0.78419$ to about four decimal places, which is consistent but not independent confirmation, since they assumed the same spine.

The random and hill-climbing figures say something only about where the worst sets are not. A search that found nothing below $0.83$ for five points has shown that bad sets of five points are rare and hard to reach, not that none exist; the chain’s five points, at $0.8155$, are a set the searches simply never came near.

Still open: the ratio of space #

Is the Steiner ratio of three-dimensional space about 0.784, attained only in the limit by the chain of tetrahedra? It is a conjecture, supported by the computations of Smith and Smith and by every search since. No set of points has been found with a lower ratio, and no proof that none exists is in sight; even the plane’s ratio, conjectured to be $\sqrt3/2$ in 1968, remains open after a published proof turned out to have a gap.

In higher dimensions the picture is the same and less settled. The regular simplex’s ratio falls with dimension, as the second figure shows, and chains built from simplices do better again in every dimension where they have been tried, but neither the worst sets nor the ratios are known. Whether the ratio of $d$-dimensional space tends to a positive limit as $d$ grows, and what that limit is, are open; the best bounds leave a wide gap between them.

Worse by repetition #

In space the regular tetrahedron is not the worst case for junctions; a chain of tetrahedra glued face to face is, as far as anyone has found. The tetrahedron’s shortest network is 81.3% of its spanning tree, and the regular simplex does worse in every added dimension — 78.4% in four, 76.5% in five. Along the chain the ratio rises at five points and then falls with every point added, to 78.6% at sixty and about 78.4% in the limit, Smith and Smith’s conjectured ratio of three-dimensional space. Random points average about 95%, searches that only go downhill stall far above the chain, and the worst case was found by reasoning about repetition rather than by search.