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 . Its length is times the side, beating the diagonal cross ().
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