Editing Steiner tree problem (section)

==Steiner ratio==

The '''Steiner ratio''' is the [[supremum]] of the ratio of the total length of the minimum spanning tree to the minimum Steiner tree for a set of points in the Euclidean plane.{{sfnp|Ganley|2004}}

In the Euclidean Steiner tree problem, the [[Gilbert–Pollak conjecture]] is that the Steiner ratio is <math>\tfrac{2}{\sqrt{3}}\approx 1.1547</math>, the ratio that is achieved by three points in an [[equilateral triangle]] with a spanning tree that uses two sides of the triangle and a Steiner tree that connects the points through the centroid of the triangle. Despite earlier claims of a proof,<ref>''The New York Times'', 30 Oct 1990, reported that a proof had been found, and that [[Ronald Graham]], who had offered $500 for a proof, was about to mail a check to the authors.</ref> the conjecture is still open.{{sfnp|Ivanov|Tuzhilin|2012}} The best widely accepted [[upper bound]] for the problem is 1.2134, by {{harvtxt|Chung|Graham|1985}}.

For the rectilinear Steiner tree problem, the Steiner ratio is exactly <math>\tfrac{3}{2}</math>, the ratio that is achieved by four points in a square with a spanning tree that uses three sides of the square and a Steiner tree that connects the points through the center of the square.{{sfnp|Hwang|1976}} More precisely, for <math>L_1</math> distance the square should be tilted at <math>45^{\circ}</math> with respect to the coordinate axes, while for <math>L_{\infty}</math> distance the square should be axis-aligned.