Two probabilistic results on rectilinear Steiner trees (Q1105495): Difference between revisions

Given a set V of n points in a plane a Rectilinear Steiner Tree (RST) is a tree that contains V as subset of its vertex set and allows only horizontal and vertical edges. The vertices of T not in V are called Steiner Points. The problem of finding an RST with minimal overall length is NP-complete. The author develops a new heuristic for the RST problem and shows that the expected length of the RST given by the new heuristic is for large n at least 0.098 \% shorter than the expected length of the minimal spanning tree heuristic. Moreover he proves: For large n, the expected number of Steiner points in the optimal solution of the RST problem is at least 0.041\(\cdot n\).