Skip to content

Shortest road network joining four square towns

Question

Four towns sit at the corners of a square. Roads must be built so that every town can reach every other, using the least total road length. What does the optimal network look like?

Short answer

A Steiner tree with two internal junctions. Two junction points on the square's centre line connect to a pair of adjacent towns each and to each other, with all roads meeting at 120∘120^\circ. Its length is (1+3)≈2.73(1+\sqrt3)\approx2.73 times the side, beating the diagonal cross (22≈2.832\sqrt2\approx2.83).

Adapted from Wilmott, Frequently Asked Questions in Quantitative Finance, ch. 10 brainteaser 'Urban planning', p.353; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution