Talk:Steiner tree problem

But what IS it? You never define what field it should be in, if it's linguistics or physics or what, or whether it might be a real tree. Help the reader and give some broad definition of this rather than just the specifics. Moncrief, 2 Mar 2004

Weighted Steiner Tree

I believe the problem description should start with the weighted Steiner tree description. I see little to no literature on the non-weighted version and in any case it's a specific case in which all weights are equal. —Preceding unsigned comment added by Gshaham (talk • contribs) 09:03, 11 December 2009 (UTC)

I don't quite see where we currently describe the non-weighted version of the problem. The lead paragraphs mention "lengths of edges", which makes sense both in the metric version (length = weight of the edge) and in the Euclidean version (length = distance between points). Anyway, I agree that we could re-organise the article and make the lead paragraphs more clear; feel free to edit it. — Miym (talk) 10:31, 11 December 2009 (UTC)

If I am not wrong the sentence "A Steiner tree is a tree in G that spans all vertices of S." is incorrect as this is a minimum spanning tree. A correct version should say that the Steiner tree is a tree in G plus the additional Steiner vertices and the additional Steiner edges, even if it is not clear to me which weight should be given to the edges that are added to the tree. — Roberto Mosca (rmosca76) (talk) 10:23, 14 February 2011 (UTC)

Minimum energy / soap bubbles

I'm surprised there is no mention of soap bubbles, which bubbles form minimum energy structures on wire frames which I *think* are 3D Steiner trees. Ian.macky (talk) 06:17, 18 February 2011 (UTC)

No, they don't create Steiner trees. This is a common misconception. The bubbles only find some *locally* minimal energy structure, which may or may not be the globally optimal Steiner tree. (BTW, the experiment is usually done in 2D, with pegs on a board. And if the bubbles happen to hit the right topology of the tree, then energy minimization actually produces the correct layout.) See Scott Aaronson's "NP complete problems and physical reality" for more. Misof (talk) 14:49, 18 April 2011 (UTC)

Steiner tree in graphs is not a generalisation

The Steiner tree in graphs is not a generalisation but in fact a special case of the Steiner tree problem:

The general case allows inclusion of Steiner points from a metric space (in the Euclidean case even a continuum), whereas the Steiner tree in graphs only from a weighted graph. A metric space with infinitely many points is not a graph, though. Conversely, a weighted graph is either a metric space (to wit if the triangle inequality holds) or can be made a metric space for the purpose of Steiner tree in graphs by ignoring edges that are longer than connections via other points. Hence, the Steiner tree problem in graphs is a special case of the Steiner tree problem in metric spaces rather than a generalisation.

Lantani (talk) 09:51, 10 April 2014 (UTC) Comments preferred either here or to my talk page in de.wikipedia

Motorway problem?

I have seen the Steiner problem also referred to as the Motorway problem (see for example https://www.youtube.com/watch?v=dAyDi1aa40E; http://search.informit.com.au/documentSummary;dn=301339078991765;res=IELHSS). — Preceding unsigned comment added by Mrincodi (talk • contribs) 06:56, 12 October 2015 (UTC)

N=3, definition of Fermat point.

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.

The second part of the sentence is improper, since as we read in Fermat point:

When a triangle has an angle greater than 120°, the Fermat point is sited at the obtuse-angled vertex.

thus, it is true in general that

The Fermat point gives a solution to the geometric median and Steiner tree problems for three points.

--Natematic (talk) 08:54, 10 June 2017 (UTC)