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:
“To many men ... the miasma of peace seems more suffocating than the bracing air of war.”
—George Steiner (b. 1929)
“Power is, in nature, the essential measure of right. Nature suffers nothing to remain in her kingdoms which cannot help itself. The genesis and maturation of a planet, its poise and orbit, the bended tree recovering itself from the strong wind, the vital resources of every animal and vegetable, are demonstrations of the self-sufficing and therefore self-relying soul.”
—Ralph Waldo Emerson (1803–1882)