9867

The Geometry of the Steiner Tree Problem for up to Five Points

We would like to find an optimal way of connecting a given finite set of points in the plane, in the sense that the total length of the line segments joining the points is minimal. This optimization problem is referred to as the Steiner tree problem. This Demonstration supports a manual search for such a network of line segments. It can be proved that an optimal network is achieved by adding some points (called Steiner points) to the original set of so-called regular points and finding the minimal spanning tree of the resulting complete graph, where the weights of the edges are the Euclidean distances between the endpoints.

SNAPSHOTS

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

DETAILS

Before reading further, I would recommend that you experiment. Choose the position of the regular points, then add some Steiner points and drag them to try to minimize the total length. See if choosing more Steiner points is helpful or not. You will soon recognize that more is not always better, and that an optimal network has very interesting geometric properties. An optimal network is not necessarily unique.
For regular points, an optimal solution depends on the points' relative positions. If they form a triangle with an angle larger than 120°, then the two shortest sides form the optimal network and no Steiner points are needed. On the other hand, if all the angles of the triangle are less than 120°, then an appropriately chosen Steiner point connected to all vertices gives the optimal network. This point is called the Torricelli point (or Fermat point) of the triangle. One way to construct this point is to draw external equilateral triangles on the sides of the triangle and to connect the third vertices of these triangles to the opposite vertices of the original triangle.
For regular points, an optimal solution again depends on their relative positions. If they spread out "nicely," a simple geometric construction involving equilateral triangles drawn on opposite sides of the quadrilateral leads to a solution. On the other hand, there are several arrangements of the original points where this construction does not give an optimal network.
For there are even more possibilities. In some cases, a clever use of circles and equilateral triangles leads to an optimal network.
In general, the Steiner tree problem using Euclidean distances is NP-complete. Finding an optimal solution or even a close-to-optimal solution is difficult. However, an optimal network always exists; it is a tree structure with finitely many Steiner points added, where all angles formed by adjacent edges are not less than 120°, and where at Steiner points exactly three edges meet.
This Demonstration intends to show how these facts help in finding an optimal case for a small number of points. It also highlights a consequence of these properties, namely, that although adding some Steiner points can be helpful, not too many are needed. For example, for , one Steiner point may not be enough, but three are certainly not needed. Try it! By trying to locate Steiner points so that in the network all angles at those points are 120°, you will better understand the concept of angles subtended by the same arc. If you find a solution that looks optimal, you can try to figure out a way to construct it with ruler and compass. For the case of and , the Related Links below show a possible solution.
In the Demonstration, the minimal spanning tree is found using Prim's algorithm; the code is a slight modification of the code used by Frederick Wu in his Demonstration about greedy algorithms for a minimal spanning tree (see the Related Links).
Reference
[1] "Steiner Tree Problem." Encyclopedia of Mathematics. www.encyclopediaofmath.org/index.php/Steiner_tree_problem.
    • 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+