Suppose we have four points in a unit square, as described in the question here. We are tasked with building a network of roads that connect all the cities. The travelling distance (T) of this network is defined as the sum of the distance you must travel along a road to get from point A to B, and point A to C, ... and all six combinations of points.

Suppose we're given a certain budget, which will enable us to construct a length L of roads. Where should we build the roads, to minimise T? And what is the relation between L and T?

As the question linked to above describes, there are no solutions possible if L < 1+√3. When L = 1+√3, it is only possible to construct one network to connect all the cities (the first option in the diagram below). Here, T = 2*(2/√3) + 4*(1+1/√3) = 4 + 8/√3 = 8.6188...

If we were given slightly more budget, the best use (I believe) would be to shift the two junction points slightly closer together. Once L = 2√2, the network simplifies to two roads, from A to C, and B to D, and now T = 6√2 (the second option in the diagram below).

Then, as L increases, the optimal network evolves - each infinitesimal unit of road seems to reduce T by approximately 0.76 units. Once L = 4 + 2√2 , we can construct a network that connects each point to the other, and T = 4 + 2√2. The diagram

But is this process which I show in the diagram the optimal process? And what would the general process be if there was a larger network of cities?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.