Exact computation of Steiner minimal trees in the plane (Q1076029)

A Steiner minimal tree for a given set \(A=\{a_ 1,...,a_ n\}\) of plane points is a tree which interconnects these points and whose total length is minimum. The tree may contain other vertices of the plain besides \(a_ 1,...,a_ n\). Several algorithms are known for construction of Steiner minimal trees but all of them are of exponential complexity. The present paper further improves the Winter's approach in such a way that all 17-point problems and most of 30-point problems can be solved in a reasonable time.