WOLFRAM NOTEBOOK

WOLFRAM|DEMONSTRATIONS PROJECT

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

Choose "regular points" below,
then the number of regular points,
3
4
5
and drag them anywhere.
Once these points are chosen, the task
is to connect them with a network
of lines so that the total length
is as small as possible.
You can use some Steiner points
where the network lines can break.
Now choose "Steiner points" and
how many you want to use.
regular points
Steiner points
0
1
2
3
You can drag them anywhere.
Can you find an optimal position of
these additional Steiner points?
For any position of the points, the
Demonstration shows a network of
line segments of mimimal total
length connecting all the points .
show the angles
The total length of the network is:
6.01064
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.
Wolfram Cloud

You are using a browser not supported by the Wolfram Cloud

Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.


I understand and wish to continue anyway »

You are using a browser not supported by the Wolfram Cloud. Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.