A Solution of the Steiner Tree Problem

The solution of a Steiner Tree Problem can be rather difficult. The reason is that unknown magnitudes of the links are functions of an unknown angle. For an example with the five points, the Ps, in the diagram below one can assume three intermediate points, the Xs, and label the seven links a through g. The tree has only three directions since there is a fixed angular separation of 120° between them and these are labeled α, β = α + π/3, and γ = α - π/3.

From the paths between the points, a-b, a-c-d, etc. we get a set of equations involving the unknown lengths and the directions (an e subscripted by one of the angles). From the way in which the paths were chosen the first three equations each introduce a new pair of unknown lengths. One can solve these equations for one pair of unknowns at a time since we can use the previously found functions for the lengths.

To solve for a pair of unknown lengths we can take the dot product of the equation with two independent vectors, in this case the unit vectors with the angles α and β, and it is useful to introduce the notation for a pair of dot products. (U V) is essentially a matrix and its product with a vector is a vector.

The resulting sets of equations for the unknown lengths are,

And by multiplying both sides by the inverse of the matrix on the left we get the linear functions for the unknown lengths.






Once the functions have been found we can then solve the last equation for the unknown angle, α.





If the points are the vertices of a pentagon, we find that α = 90° and we get a plot that looks more like a honey comb structure.