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)$.
Answer
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
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.
No comments:
Post a Comment