A decomposition theorem on Euclidean Steiner minimal trees (Q1112056): Difference between revisions

Given a set F of points on the Euclidean plane a Steiner minimal tree (SMT) is a shortest tree interconnecting F. The paper proves the following new decomposition theorem enabling in some cases to reduce the complexity of the problem. Theorem: Let P(F) denote the Steiner polygon bounding the Steiner hull of the given set of points F. Let A, B, C, D be four points on P(F) satisfying: (i) P(A,B,C,D) is a convex quadrilateral, (ii) \(\sphericalangle A\geq 120\circ \leq\sphericalangle B\), (iii) let 0 be the intersection of the two diagonals [A,C] and [B,D]. Then \(\sphericalangle B0A\geq\sphericalangle A+\sphericalangle B-150\circ.\) Then no part of the SMT on F can be inside of P(A,B,C,D), i.e., the SMT on F is a union of the SMT on \(F_ 1\), the SMT on \(F_ 2\) and the edge [A,B] \((F_ 1\) and \(F_ 2\) are subsets of F which are ``separated'' by P(A,B,C,D)).