Editing Steiner tree problem (section)

==Euclidean Steiner tree==
{{regular_polygon_minimum_spanning_tree.svg}}
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 (geometry)|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 segment]]s either directly or via other [[Point (geometry)|points]] and line segments.

While the problem is named after Steiner, it has first been posed in 1811 by [[Joseph Diez Gergonne]] in the following form: "A number of cities are located at known locations on a plane; the problem is to link them together by a system of canals whose total length is as small as possible".<ref>Marcus Brazil, Ronald L. Graham, Doreen A. Thomas and Martin Zachariasen, "On the history of the Euclidean Steiner tree problem", {{JSTOR|24569605}}</ref>

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.

The problem for {{math|1=''N''&nbsp;=&nbsp;3}} has long been considered, and quickly extended to the problem of finding a [[star (graph theory)|star network]] with a single hub connecting to all of the ''N'' given points, of minimum total length.
However, although the full Steiner tree problem was formulated in a letter by [[Carl Friedrich Gauss|Gauss]], its first serious treatment was in a 1934 paper written in Czech by [[Vojtěch Jarník]] and {{ill|Miloš Kössler|cs}}. This paper was long overlooked, but it already contains "virtually all general properties of Steiner trees" later attributed to other researchers, including the generalization of the problem from the plane to higher dimensions.<ref>{{citation
 | last1 = Korte | first1 = Bernhard | author1-link = Bernhard Korte
 | last2 = Nešetřil | first2 = Jaroslav | author2-link = Jaroslav Nešetřil
 | doi = 10.1016/S0012-365X(00)00256-9
 | issue = 1–3
 | journal = Discrete Mathematics
 | mr = 1829832
 | pages = 1–17
 | title = Vojtěch Jarnik's work in combinatorial optimization
 | volume = 235
 | year = 2001| hdl = 10338.dmlcz/500662
 | hdl-access = free
 }}.</ref>

For the Euclidean Steiner problem, points added to the graph ([[Steiner point (computational geometry)|Steiner points]]) must have a [[Degree (graph theory)|degree]] of three, and the three edges incident to such a point must form three 120 degree angles (see [[Fermat point]]). It follows that the maximum number of Steiner points that a Steiner tree can have is {{math|1=''N''&nbsp;&minus;&nbsp;2}}, where ''N'' is the initial number of given points. (all these properties were established already by Gergonne.)

For ''N'' = 3 there are two possible cases: if the triangle formed by the given points has all angles which are less than 120 degrees, the solution is given by a Steiner point located at the [[Fermat point]]; otherwise the solution is given by the two sides of the triangle which meet on the angle with 120 or more degrees.

For general ''N'', the Euclidean Steiner tree problem is [[NP-hard]], and hence it is not known whether an [[Optimization problem|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.{{sfnp|Crescenzi|Kann|Halldórsson|Karpinski|2000}} It is not known whether the Euclidean Steiner tree problem is NP-complete, since membership to the complexity class NP is not known.