On stars and Steiner stars

摘要

A Steiner star for a set P of n points in Rd 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 times longer than the minimum Steiner star for any finite point configuration in Rd. The maximum ratio between them, over all finite point configurations in Rd, is called the star Steiner ratio in Rd. 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--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.