Steiner tree problem

Steiner problem

Given a set $P$ of points in a metric space, the problem is to find a shortest network connecting all the points in the set. An optimal solution to this problem is called a Steiner minimum tree for $P$. The Steiner minimum tree may well have some vertices that are not in $P$. Such vertices are called Steiner nodes or Steiner points, and the other points are called regular points. These points should not be confused with the Steiner point of a convex body.

For subsets of networks, the Steiner tree problem is a special network optimization problem. The Steiner tree problem is $\mathcal{NP}$-hard.

A Steiner minimum tree in the Euclidean plane $E^2$ has the following properties:

1) all leaves are regular points;

2) every two edges meet at an angle of at least $120^\circ$;

3) every Steiner point has degree at least three.

A tree satisfying these three conditions and connecting all points of $P\subset E^2$ (as regular points) is called a Steiner tree.

The Steiner ratio is the ratio between the length of a minimum Steiner tree and a shortest spanning tree (see Tree). The Gilbert–Pollak conjecture [a3] says that the Steiner ratio of the Euclidean plane is $\sqrt3/2$; it was proved in [a2].

References

[a1]	Ding-Zhu Du, "Minimax and its applications" R. Horst (ed.) P.M. Pardalos (ed.) , Handbook of Global Optimization , Kluwer Acad. Publ. (1995) pp. 339–368
[a2]	Ding-Zhu Du, F.K. Hwang, "A proof of the Gilbert–Pollak conjecture" Algorithmica , 7 (1992) pp. 121–135
[a3]	E.N. Gilbert, H.O. Pollak, "Steiner minimal trees" SIAM J. Appl. Math. , 16 (1968) pp. 1–29