On stars and Steiner stars

ABSTRACT

For a set of n points in the plane, a star connects one of the points (the center) to the other n - 1 points by straight line edges, while a Steiner star connects an arbitrary point in the plane to all n input points. The center of the minimum Steiner star, the Weber center, minimizes the sum of distances from the n points. 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 the plane or 3-space. The maximum ratio between the two is conjectured to be 4/π in the plane and 4/3 in three dimensions. Here we improve the upper bound to 1.3999 in the plane, and to √2 - 10^-4 in 3-space. 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 relies on constructing a suitable discretization for a continuous problem and then using linear programming to optimize over a relatively large set of constraints.

REFERENCES

• 1: 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]
• 2: V. Boltyanski, H. Martini, and V. Soltan, Geometric methods and optimization problems, Kluwer Acad. Publ., 1999.
• 3: 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]
• 4: Peter Brass, The maximum number of second smallest distances in finite planar sets, Discrete & Computational Geometry, v.7 n.4, p.371-379, 1992 [doi>10.1007/BF02187849]
• 5: 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]
• 6: E. J. Cockayne and Z. A. Melzak, Euclidean constructibility in graph-minimization problems, Mathematical Magazine 42 (1969), 206--208.
• 7: 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.
• 8: A. Dumitrescu and Cs. D. Tóth, Distinct triangle areas in a planar point set, in Proc. 12th Conf. on Integer Prog. and Combin. Optimization (Ithaca, NY, 2007), vol. 4513 of LNCS, Springer, pp. 119--129.
• 9: D. Eppstein, Spanning trees and spanners, in Handbook of Computational Geometry (J.-R. Sack and J. Urrutia, eds.), Elsevier, Amsterdam, 2000, pp. 425--461.
• 10: S. Fekete and H. Meijer, On minimum stars and maximum matchings, Discrete & Computational Geometry 23 (2000), 389--407.
• 11: 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
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.3 Applications

General Terms:
Algorithms, Design, Theory