12
$\begingroup$

Four guard towers are situated in a square formation of side length 1km. A general wants to build roads to connect the towers so that one can walk from any tower to any tower along the roads, possibly passing through towers. The size of the towers is too small to matter; think of them as points.

What is the smallest total length of road that suffices? For example, one can build roads along three of the sides of the square for a total length of 3km, but better is possible.

Stating it mathematically, your goal is find a finite collection of line segments with total length as small as possible such that their union is connected and contains points $(0,0),(0,1),(1,0),(1,1)$.

| improve this question | |
$\endgroup$
20
$\begingroup$

The problem is basically asking for a minimum Steiner tree. For points located at the corners of a square, the solution consists of five lines. Four of them connect to the corners, and one connects the other four lines in two vertices of degree 3. I found a picture of the solution in this MathOverflow question enter image description here
So the minimum length is 1 + √3 ≈ 2.73. Note that at the vertices of a Steiner tree (in general) all angles are 2π/3 or 120 degrees, to ensure that each point is at a local minimum.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This is the correct answer. +1 $\endgroup$ – GOTO 0 Nov 9 '14 at 22:33
  • 2
    $\begingroup$ This is the optimal configuration. Note that like in all Steiner Trees, the junctions of three segments have them meet at 120 degree angles for that point to be a local optimum. $\endgroup$ – xnor Nov 9 '14 at 22:37
  • $\begingroup$ @xnor Ah I wanted to add that, will edit. $\endgroup$ – Martin Ender Nov 9 '14 at 22:38
  • 2
    $\begingroup$ You can do this with soap. $\endgroup$ – Renae Lider Nov 10 '14 at 9:48
  • $\begingroup$ @RenaeLider Indeed, but what that article doesn't seem to mention is that could give you a local but non-global minimum. (In fact, I first encountered Steiner trees in exactly the context of analogue computation.) $\endgroup$ – Martin Ender Nov 10 '14 at 10:52
2
$\begingroup$

Connect towers diagonally using 2 roads each of length √2 km. You can reach any tower from any other tower using the crossroad in the middle. The total road length will be 2√2 ≈ 2.83 km.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Sorry this is suboptimal. $\endgroup$ – smci Nov 10 '14 at 5:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.