On stars and Steiner stars

摘要

A Steiner star for a set P of n points in R-d connects an arbitrary point in R-d to all points of P, while a star connects one of the points in P to the remaining n - 1 points of P. All connections are realized by straight line segments. Let the length of a graph be the total Euclidean length of its edges. Fekete and Meijer showed that the minimum star is at most root 2 times longer than the minimum Steiner star for any finite point configuration in R-d. The supremum of the ratio between the two lengths, over all finite point configurations in R-d, is called the star Steiner ratio in R-d. It is conjectured that this ratio is 4/pi = 1.2732... in the plane and 4/3 = 1.3333... in three dimensions. Here we give upper bounds of 1.3631 in the plane, and 1.3833 in 3-space. These estimates yield improved upper bounds on the maximum ratios between the minimum star and the maximum matching in two and three dimensions. We also verify that the conjectured bound 4/pi in the plane holds in two special cases. Our method exploits the connection with the classical problem of estimating the maximum sum of pairwise distances among n points on the unit sphere, first studied by Laszlo Fejes Toth. It is quite general and yields the first nontrivial estimates below root 2 on the star Steiner ratios in arbitrary dimensions. We show, however, that the star Steiner ratio in R-d tends to root 2 as d goes to infinity. As it turns out, our estimates are related to the classical infinite Wallis product: pi/2 = Pi(infinity)(n=1) (4n(2)/4n(2)-1) = 2/1 . 2/3 . 4/3 . 4/5 . 6/5 . 6/7. 8/7 . 8/9 ....