Concept

Steiner tree

The shortest network joining a set of points when extra junction points may be added anywhere. Every junction meets exactly three roads at 120°, there are at most two fewer junctions than points, and finding the best arrangement is NP-hard.

Named by 4 essays across 2 fields — each of them below, with the objects they name alongside it.

The point nearest in total to three corners, and the lines that find it. A triangle with equilateral triangles on its sides, the three lines from each corner to the opposite apex meeting at the Fermat point, where the sides subtend 120°; least total distance 7.7090.

The point nearest in total to three corners

Three towns want one depot with the least total road to all of them. The answer is not the centroid or any of the classical centres: it is the point from which every side of the triangle is seen at 120°, found by building equilateral triangles on the sides. Three straight lines through it have the same length, and that length is the least total. When an angle of the triangle reaches 120°, the answer jumps to that corner — and the same 120° rule shapes soap films and the shortest networks joining many points.

geometry · Triangle centres
Seven towns joined with junctions and without. Seven random points: spanning tree 1.65407, Steiner tree 1.54997 with 2 junctions, ratio 0.93707.

What a junction can save

Join a set of towns by roads that may meet only at towns, and the shortest such network is easy to find. Allow junctions anywhere and the network gets shorter — but never, it is conjectured, by more than 13.4%, the saving the Fermat point makes on an equilateral triangle. Computed exactly on 1,304 random sets of up to seven towns, the average saving is about 3%. An adversarial search drives it down to the bound and no further, and a hexagon with its centre attains it exactly. The proof of the bound that was accepted for twenty years has a gap.

geometry · Triangle centres
What junctions save in space. tetrahedron SMT/MST 0.81305; 12-point helix 0.79472.

A chain of tetrahedra saves more

In the plane, junctions never seem to shorten a network of roads by more than the equilateral triangle's 13.4%. In space the regular tetrahedron allows 18.7%, and the obvious guess — that it is the worst case, as the triangle is in the plane — is wrong. Points spaced along a chain of tetrahedra glued face to face do better with every point added: 20.5% at twelve, 21.4% at sixty, and about 21.6% in the limit. Random points come nowhere near, and a search that only goes downhill does not find the chain.

geometry · Triangle centres
Four walls that stop every line through a square. Opaque barriers for the unit square, all verified over 1440 directions: three sides 3.00000; two diagonals 2.82843; Steiner tree on all four 2.73205; three corners and a stub 2.63896.

The shortest wall that stops every line

A straight cable runs somewhere under a square field, and a trench has to find it for certain. Three sides of the field will do, at length 3. Two diagonals cost 2.83, and a Steiner tree 2.73. The best trench known has length 2.6390 and comes in two pieces that do not touch. Averaging over lines proves nothing shorter than 2 can work, and in over a century the gap between the two numbers has hardly moved.

analysis · Arc length

Named alongside it

The objects these essays reach for when they reach for this one.

OptimisationConjectureEquilateral triangleSpanning treeArc lengthConvexityDimensionExhaustive searchExtremal problemIntegral geometryLower boundNapoleons theorem

All concepts