Steiner tree problems (Q1187352): Difference between revisions

Three problems are introduced. The first problem generalizes the Gilbert- Pollak conjecture in the following way: For a given finite point set \(P\) define the ``greedy tree'' \(\text{GT}(P)\) as follows: Start with the points as a forest of 1-node trees; at any stage add the shortest possible line segment to the current forest, which causes two trees to merge; continue until the forest becomes a tree. Conjecture: \[ \inf_ P{\text{length\;SMT}(P)\over\text{length\;GT}(P)}=2\sqrt 3/(2+\sqrt 3)\approx 0.92820, \] where \(\text{SMT}(P)\) denotes a Steiner Minimal Tree for \(P\). Problem 2 gives an idea to introduce point-equivalences so that finding Steiner Minimal Trees becomes trivial. This implies lower bounds for the length of Steiner Trees in Euclidean \(d\)-space. Problem 3 asks for the relation between the length of a Steiner Minimal Tree and the length of the union of all Steiner Minimal Trees for a given point set.