Talk:Steiner tree problem

Untitled

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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[reply]

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)[reply]

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)[reply]

Reorganizing this topic

I think this page could be reorganized to be clearer. There are two types of "Steiner tree" problems: the graph problem and the geometric or Euclidean problem. The article covers this point, but it jumps back and forth between them, and tends to go into much more detail about the graph problem. The rectilinear tree problem has its own page even though it is a restricted version of the Euclidean problem. That the graph problem and Euclidean problems are two different areas of study is apparent from the research, which tends to be about, and refer to previous research about, either one or the other. I'd like to create separate pages for the graph and Euclidean problems, then change "Steiner tree problem" to cover the differences between the problems and any common elements. Thoughts? WillisBlackburn (talk) 22:35, 26 October 2024 (UTC)[reply]

@David Eppstein: AFAIU there are no "two types" of Steiner trees: all of them are on graphs, only of different categories. --Altenmann >talk 00:54, 28 October 2024 (UTC)[reply]

No, WillisBlackburn is correct. The Euclidean Steiner tree problem is for points in the plane, not graphs. The difference is that you can add new Steiner points to a point set, but you cannot add new vertices to a graph. It is not obvious a priori that you can turn a Euclidean Steiner tree instance into an equivalent finite graph, without solving the problem first, and I don't know of a way of doing this that doesn't produce superexponentially many vertices.

I agree that these should be separate articles, with some kind of set index article as the landing page for the undisambiguated name. I think "Euclidean Steiner tree" and "graph Steiner tree" are adequate names, to go with "rectilinear Steiner tree". It wouldn't be problematic to add the word "problem" but I'm not convinced it adds much meaning to the name. —David Eppstein (talk) 03:14, 28 October 2024 (UTC)[reply]