On stars and Steiner stars: II

ABSTRACT

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 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 R^d, 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--10⁻⁴, 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 László Fejes Tóth. It is quite general and yields the first nontrivial estimates below √2 on the star Steiner ratios in arbitrary dimensions. We show, however, that the star Steiner ratio in R^d tends to √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: [EQUATION]

REFERENCES

• 1: R. Alexander: On the sum of distances between n points on a sphere, Acta Mathematica Academiae Scientiarum Hungaricae 23 (1972), 443--448.
• 2: R. Alexander: On the sum of distances between n points on a sphere. II, Acta Mathematica Academiae Scientiarum Hungaricae 29 (1977), 317--320.
• 3: J. Ralph Alexander , József Beck , William W. L. Chen, Geometric discrepancy theory and uniform distribution, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 4: R. Alexander and K. Stolarsky: Extremal problems of distance geometry related to energy integrals, Transactions of the American Mathematical Society 193 (1974), 1--31.
• 5: Chanderjit Bajaj, The algebraic degree of geometric optimization problems, Discrete & Computational Geometry, v.3 n.2, p.177-191, Jan, 1988 [doi>10.1007/BF02187906]
• 6: G. Björck: Distributions of positive mass which maximize a certain generalized energy integral, Arkiv för Matematik 3 (1956), 255--269.
• 7: V. Boltyanski, H. Martini, and V. Soltan: Geometric Methods and Optimization Problems, Kluwer Acad. Publ., 1999.
• 8: Prosenjit Bose , Anil Maheshwari , Pat Morin, Fast approximations for sums of distances, clustering and the Fermat--Weber problem, Computational Geometry: Theory and Applications, v.24 n.3, p.135-146, April 2003 [doi>10.1016/S0925-7721(02)00102-5]
• 9: R. Chandrasekaran , A. Tamir, Algebraic optimization: the Fermat-Weber location problem, Mathematical Programming: Series A and B, v.46 n.2, p.219-224, Feb. 1990 [doi>10.1007/BF01585739]
• 10: E. J. Cockayne and Z. A. Melzak: Euclidean constructibility in graph-minimization problems, Mathematical Magazine 42 (1969), 206--208.
• 11: Z. Drezner, K. Klamroth, A. Schöbel, and G. O. Wesolowsky: The Weber problem, in Facility Location: Applications And Theory (H. W. Hamacher and Zvi Drezner, eds.), Springer, Berlin, 2002, pp. 1--36.
• 12: Adrian Dumitrescu , Csaba D. Tóth, On stars and Steiner stars, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1233-1240, January 20-22, 2008, San Francisco, California
• 13: D. Eppstein: Spanning trees and spanners, in Handbook of Computational Geometry (J.-R. Sack and J. Urrutia, eds.), Elsevier, Amsterdam, 2000, pp. 425--461.
• 14: L. Fejes Tóth: On the sum of distances determined by a pointset, Acta Mathematica Academiae Scientiarum Hungaricae 7 (1956), 397--401.
• 15: S. Fekete and H. Meijer: On minimum stars and maximum matchings, Discrete & Computational Geometry 23 (2000), 389--407.
• 16: G. H. Hardy and E. M. Wright: An Introduction to the Theory of Numbers, fifth edition, Oxford University Press, 1979.
• 17: H. Martini, K. Swanepoel, and G. Weiss, The Fermat-Torricelli problem in normed planes and spaces, Journal of Optimization Theory and Applications 115(2) (2002), 283--314.
• 18: E. Weiszfeld: Sur le point pour lequel les sommes des distances de n points donné est minimum, Tôhoku Mathematical Journal 34 (1937), 355--386.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory