Four cities stand at the corners of a square.

geometry/steiner.tree New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Four cities stand at the corners of a square.  What road system of
least total length lets you travel from any city to any other?

There are four cities that form a square as so:

A       B



C       D

Your job is to lay out a road system, with the least amount of
roadway, such that you can travel from any one city to another, without
traveling through a third city.  An "X" is not the answer.

-- James Allen <vivisectvi@geocities.com>

Show solution

This is a simple Steiner Tree problem.  In a minimum spanning tree, we
have to connect the vertices in a graph by selecting a subset of the
(possibly weighted) arcs connecting them.  In a Steiner tree, we can
add and remove vertices at will.  In addition, there is the
Rectilinear Steiner tree problem, in which case the additional vertices
must be added at either the same x or y value as a given point and all
arcs must be either vertical or horizontal.  Computer manufacturers
(among others) are _very_ interested in improvements to the solutions
to these problems.

As you might guess, the Steiner tree problem is np-complete, but is
still a fun problem to work on.  My co-worker presently has the world's
record for solved Steiner Tree problems at over a thousand and just
presented a paper in Switzerland.  Pretty cool stuff, considering that
a couple of years ago the record was in the double digits and people
were not expecting such an increase for many years.

Anyway, the solution to this particular problem, and, in fact, to any
three point Steiner tree problem (the square is a special case) is
given below:

Ok, here we go.  Start with the following situation, where we want to
solve the 3-point Steiner tree problem for BDG:


      G
                     B



                     D


Take the distance BD and make an equilateral triangle to the right,
resulting in the triangle BDE


      G
                     B

                           E

                     D


Find the center of the equilateral triangle and draw a circle through
BDE.  Then, draw a line from E to G.  The EG line is called the
Simpson line, after the person who discovered this geometric solution:


      G--
         \----\  /--B--\
               -S----   \
                |    \---E
                \       /
                 \--D--/

Where the EG line intersects the circle is our Steiner point, S, and
lines from B, D, and G meet there.  This is our solution:


      G--
         \----\    -B
               -S-/
                 \
                  \
                   D


In the square problem, we know that the Steiner point lies along the
bisection of the square.  Applying the same method as above we get:


 A      B
  \    /
   +--+
  /    \
 C      D

And it is simple enough to show that the angles around the Steiner
points '+' are 120 degrees.  If the distance from A to B is L, then the
total length is:

        L ( 1 + sqrt(3) ) =~  2.732 * L


An alternative approach to solving the problem is to simply create a
formula for the length of the arcs and use calculus to minimize it.

-- Clark Dorman <clark@s3i.com>