On stars and Steiner stars. II

摘要

A Steiner star for a set P of n points in R~d connects an arbitrary center point to all points of P, while a star connects a point p ∈ P to the remaining n ? 1 points of P. All connections are realized by straight line segments. Fekete and Meijer showed that the minimum star is at most 2~(1/2) times longer than the minimum Steiner star for any finite point configuration in R~d. The maximum ratio between them, over all finite point configurations in Rd, is called the star Steiner ratio in R~d. It is conjectured that this ratio is 4/π = 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, thereby substantially improving recent upper bounds of 1.3999, and 2~(1/2) - 10~(-4), respectively. Our results also imply improved bounds on the maximum ratios between the minimum star and the maximum matching in two and three dimensions. 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 2~(1/2) on the star Steiner ratios in arbitrary dimensions. We show, however, that the star Steiner ratio in R~d tends to 2~(1/2), the upper bound given by Fekete and Meijer, as d goes to infinity. Our estimates on the star Steiner ratios are therefore much closer to the conjectured values in higher dimensions! As it turns out, our estimates as well as the conjectured values of the Steiner ratios (in the limit, for n going to infinity) are related to the classical infinite Wallis product: π/2 = Π((4n~2)/(4n~2-1))=(2/1)·(2/3)·(4/3)·(4/5)·(6/5)·(6/7)·(8/7)·(8/9)…(n from 1 to ∞).