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)$.


2 Answers 2


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.

  • $\begingroup$ This is the correct answer. +1 $\endgroup$
    – GOTO 0
    Commented Nov 9, 2014 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
    Commented Nov 9, 2014 at 22:37
  • $\begingroup$ @xnor Ah I wanted to add that, will edit. $\endgroup$ Commented Nov 9, 2014 at 22:38
  • 2
    $\begingroup$ You can do this with soap. $\endgroup$ Commented Nov 10, 2014 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$ Commented Nov 10, 2014 at 10:52

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.

  • 3
    $\begingroup$ Sorry this is suboptimal. $\endgroup$
    – smci
    Commented Nov 10, 2014 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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