A,B,C and D are four cities such that ABCD has the precise shape of a square with each side equal to 100 kilometers.
A railway network needs to be constructed connecting all the cities. Determine the minimum total length of this network. Prove that this is indeed the minimum network length.
From memory I know that the optimal network would have all its nodes such that at each one of them three lines meet at 120° angles. This is usually illustrated with soap bubbles with dihedral angles, and of course the planar solution follows in cross section.
So two cities that are adjacent (share a side of the square), say A and B are connected by a broken line that indents into the square, forming the two equal sides of an isosceles triangle with a vertex angle of 120°. The same is done for C and D. Then a line segment joins the two vertices.
The network's total length if four times the hypotenuse of a 60° right triangle whose longer leg is 50 km, plus the distance separating the two inner junctions, which is 100 km minus twice the shorter leg of the given right triangle.
That's 4*(2/sqrt(3))*50 + 100  2*50/sqrt(3) ~= 273.205080756888 km.
It's also 4*50/sin(60°) + 100  2*50/tan(60°).
As for this being the minimum, let's at least determine that it's the minimum of its kindthat is, two opposite sides of the square being indented to form two segments, where these pairs of segments are connected with a straight linea straight line that might vanish to zero length if brought to the center, i.e., the network being the two diagonals of the square.
That latter possibility would have total length 2*100*sqrt(2) ~= 282.84271247462, which is clearly bested by what we have above.
The opposite extreme would be an H shape of total length 3*100 = 300: even worse.
Let's see if 60° is optimal for the half of the angle at the bend in the outer track on either side.
Simplified we get:
100 + 200/sin(pi/3)  100/tan(pi/3)
in radians.
We need to differentiate:
100 + 200/sin(x)  100/tan(x)
at x = pi/3
The derivative is:
200*cos(x)/(sin(x)^2) + 100*(sec(x)^2)/(tan(x)^2)
at pi/3 this is:
200*(1/2)/(3/4) + 100*4/3 = 400/3 + 400/3 = 0
It's certainly a local extremum, and the endpoints mentioned above hint strongly that this extremum is a minimum rather than a maximum. Rather than differentiate again, a table should suffice to show this is a minimum:
halfangle total
in degrees network length
50 277.1714947
51 276.3735099
52 275.6750804
53 275.0717266
54 274.5593427
55 274.1341639
56 273.7927380
57 273.5318992
58 273.3487455
59 273.2406175
60 273.2050808
61 273.2399084
62 273.3430670
63 273.5127026
64 273.7471292
65 274.0448180
66 274.4043872
67 274.8245939
68 275.3043260
69 275.8425952
70 276.4385311

Posted by Charlie
on 20130405 15:46:00 