0
$\begingroup$

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?

$\endgroup$

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.