9873

Constructing a Steiner Tree for Five Points

For a finite number of points in the plane, there is always a network of line segments connecting them with minimal total length. Finding this network is referred to as the Steiner tree problem. This optimal network can be achieved by adding some new points in the plane and connecting some of the points with line segments.
This Demonstration illustrates a construction that approximates the optimal network for five points. It works for some arrangements of the five points, but is not general enough to solve the problem in all cases. You can drag points, but sometimes a message appears that no solution is found. This does not mean that there is no optimal network; it means that the construction illustrated cannot find it.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

The snapshots illustrate the steps of the construction, which are based on drawing equilateral triangles on two sides of the pentagon formed by the five points.
Snapshot 1: To start, choose the two sides. This is done using the "setup" controls. The order of the endpoints are important because there are two ways of drawing an equilateral triangle on a line segment. Also, because of later steps in the construction, the order of the pairs is also important. A typical case where the construction works is when the points form a convex pentagon and the points for the pairs are chosen counterclockwise.
Snapshot 2: For step 1, draw equilateral triangles on the two chosen sides.
Snapshot 3: The two new vertices of the equilateral triangles and the so-far unused vertex of the pentagon form a triangle. Step 2 finds the Fermat (or Torricelli) point of this triangle (see the Related Links section). This is the first step where the construction can fail: this point must be inside the triangle. If it is not inside, the construction fails.
Snapshot 4: Connect this Fermat point with the vertices of the equilateral triangles and find where these line segments intersect the circumcircles of the equilateral triangles. If these intersection points are not at the right position (on the smaller arc of the circle), the construction cannot continue.
Snapshot 5: To get the Steiner tree, connect the points found with the original points.
Snapshot 6: This shows the Steiner tree without the construction lines. Also, you can turn the display of the total length of the network on and off. Drag the points. It is interesting to see the positions when the construction fails to give a result. In this snapshot, the tree is built using the initial pairs and . There are other pairs for which the construction gives a solution, for example and , or and , and so on. The total lengths of the corresponding networks are not necessarily the same. Try it.
Do you see the similarity of this construction and the one for three and four points (see Related Links)? Can you figure out a way that works for six points?
Can you prove that at the junction points the line segments meet at 120°? This is why the networks found are locally optimal, in the sense that moving any junction point a bit will increase the total length of the network. This only means that the total distance cannot be improved by moving the junction points a bit; in other words the construction gives a locally optimal solution. It does not mean that a completely different construction cannot give a better network. However, it is generally true that the globally optimal network has the property that the angle between any two adjacent line segments is not less the 120° and at any added points exactly three line segments meet at 120°. In some arrangements of the original points this means that one of the local minima found with this construction (with different starting pairs) will give the globally optimal network.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+