Connecting square vertexes with minimal road I have four cities in $A=(0,0),B=(1,0),C=(1,1),D=(0,1)$. I am asked to build the shortest motorway to connect the cities. How can I do that?
I was thinking that first I need some compactness argument to prove that there really is the shortest way to connect cities. Or if one can prove that one can travel via finitely many line segments, the existence of minimal way migth be possible to prove via some olympiad-level inequalities.
Then I think I need to find points $E,F$ such that $\angle AEB=\angle CFD=120^\circ$. But I think it is difficult to prove that such a configuration is really a minimal.
Could anyone give hints/solution how to fill the details?
Bonus: Has anyone generalized this problem to $n$ cities in a regular $n$-gon?
 A: Perhaps a simpler way to see the solution:
Let there be an optimal motorway connecting all the cities.  It is clear that the road from A to C must lie within the square, similarly the road from D to B.  Hence these roads must intersect in possibly multiple points.  Let the first such point be P and the last Q.  (A diagram may help at this point).
Now, it is sufficient to have the motorway consisting of straight lines AP, DP, PQ, QC, QB. as all other paths will be longer.  Further, considering a vertical line through P, it is clear (say from the reflection principle) that P should be equidistant from A and D, otherwise AP+DP would be longer.  Similarly Q should be equidistant from B and C.  This would also give a lower PQ than otherwise, so the optimal arrangement must have P and Q on the line $y=\frac12$.
So let P have coordinates $(x, \frac12)$.  Then by symmetry, Q must have coordinates $(1-x, \frac12)$.  The total distance is then AP+DP+PQ+QC+QB = $4\sqrt{x^2+\frac14}+1-2x$.  You can minimise this using calculus to get the minimum distance as $1+\sqrt3$, when $x = \frac1{2\sqrt3}$.
A: With a single additional point you cannot do better than $2\sqrt{2}=2.828\ldots$ With two additional points (and roads departing from them forming angles of $120^\circ$, since this is the optimal configuration by the properties of the Fermat-Torricelli-Steiner point of a triangle) we may achieve a length equal to $1+\sqrt{3}=2.732\ldots$:

Then you just have to prove that there is no gain in using three or more additional points.
You can also get convinced of the minimality of the depicted configuration by using soap films.
A: Given @Henning Makholm's input, I have to revise my answer to an X connecting the four cities, with an intersection in the middle.  
This problem is reminiscent of the famous traveling salesman problem.  
If I now actually understand this question ;p then it's interesting how miserably greedy algorithms would fail.  
As for adding more details, I think that you should approach it by starting with only a single connection, and adding a single connection at a time.  The question at each step is whether a given connection your adding is optimal or not.  
