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:
“It is not the literal past that rules us, save, possibly, in a biological sense. It is images of the past.... Each new historical era mirrors itself in the picture and active mythology of its past or of a past borrowed from other cultures. It tests its sense of identity, of regress or new achievement against that past.”
—George Steiner (b. 1929)
“Behold I have given you every herb bearing seed which is upon the face of all the earth, and every tree, in which is the fruit of a tree yielding seed; to you it shall be for meat.”
—Bible: Hebrew Genesis 1:29.
But in a later context, God told the disgraced Adam, “and thou shalt eat the herb of the field” (Genesis 3:18)