Euclidean Steiner Tree
The original problem was stated in the form that has become known as the Euclidean Steiner tree problem or geometric Steiner tree problem: Given N points in the plane, the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments.
It may be shown that the connecting line segments do not intersect each other except at the endpoints and form a tree, hence the name of the problem.
For the Euclidean Steiner problem, points added to the graph (Steiner points) must have a degree of three, and the three edges incident to such a point must form three 120 degree angles. It follows that the maximum number of Steiner points that a Steiner tree can have is N − 2, where N is the initial number of given points.
For N = 3, solution is given by a Steiner point located at the Fermat point of the triangle formed by the given points.
For general N, the Euclidean Steiner tree problem is NP-hard, and hence it is not known whether an optimal solution can be found by using a polynomial-time algorithm. However, there is a polynomial-time approximation scheme (PTAS) for Euclidean Steiner trees, i.e., a near-optimal solution can be found in polynomial time.
Read more about this topic: Steiner Tree Problem
Famous quotes containing the words steiner and/or tree:
“The variables are surprisingly few.... One can whip or be whipped; one can eat excrement or quaff urine; mouth and private part can be meet in this or that commerce. After which there is the gray of morning and the sour knowledge that things have remained fairly generally the same since man first met goat and woman.”
—George Steiner (b. 1929)
“Cynicism is the humour of hatred.”
—Herbert Beerbohm, Sir Tree (1853–1917)