0.3 The steiner tree problem

Introduction

Given a set of points, called terminals, a spanning tree is the set of terminals plus a number of edges, in which two terminals connected by exactly one simple path. The problem of the minimal spanning tree is to find the shortest spanning tree, where the length of a tree is the sum of the lengths of its edges. In some cases, points in addition to the original set, called Steiner points, can be carefully placed so that the spanning tree connecting the new Steiner points and the original set of points is shorter than any tree that could be created by adding, removing, or moving any Steiner point. The resulting spanning tree is called a Steiner tree.

The Michell truss problem begins with a set of point forces, which can be viewed as points in the Steiner tree problem. Because shorter beams cost less than longer beams of the same weight, it is beneficial to minimize the length of the beams used in a truss. Applications of the Steiner tree problem may help optimize a truss by minimizing the length of its beams.

Definition

The Toricelli point of a triangle, also called the Fermat point, is found by constructing two equilateral triangles on any three sides of the triangle, and drawing a line from the new vertex of each equilateral triangle to the opposite vertex of the original triangle. The location where these two lines intersect is the Toricelli point.

Each triangle has exactly one Toricelli point. In an acute triangle, the Toricelli point is inside the triangle, and the lines from the Toricelli point to each vertex of the triangle create ${120}^{\circ }$ angles. Toricelli proved the shortest path connecting all three vertices of a triangle consists of three lines, each from the Toricelli point of the triangle to a vertex of the triangle.

Theorem 1

No two edges of a Steiner tree can meet at an angle less than ${120}^{\circ }$ .

Proof

If the two edges meet at an angle of less than ${120}^{\circ }$ , then select points on the edges that are equidistant from the vertex, and locate a new Steiner point at the Torricelli point of the triangle created by the vertex and the two selected points. Because the triangle is acute, the three new edges created by connecting the Toricelli point to the vertices of the triangle must be shorter in sum than the total length of the original two edges.

Theorem 2

A Steiner tree has no crossing edges.

Proof

If a Steiner tree had crossing edges, the cross would create at least two angles less than or equal to ${90}^{\circ }$ .

Definition

The degree of a point in a tree is defined as the number of edges connected to that point.

Theorem 3

Each Steiner point of a Steiner tree is of degree 3.

Proof

From Theorem 1, no two edges meet at an angle of less than ${120}^{\circ }$ , so the Steiner point can be of degree 3 at most. A Steiner point of degree 1 can simply be eliminated, as it creates an unnecessary edge, and a Steiner point of degree 2 can just be replaced with a straight line. Therefore a Steiner point must be of degree 3.

Theorem 4

A Steiner tree connecting $n$ terminals contains at most $n-2$ Steiner points.