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:
“Words that are saturated with lies or atrocity, do not easily resume life.”
—George Steiner (b. 1929)
“There is hardly an American male of my generation who has not at one time or another tried to master the victory cry of the great ape as it issued from the androgynous chest of Johnny Weissmuller, to the accompaniment of thousands of arms and legs snapping during attempts to swing from tree to tree in the backyards of the Republic.”
—Gore Vidal (b. 1925)