On Minimum Stars, Minimum Steiner Stars, and Maximum Matchings

Fekete, Sandor P. and Meijer, Henk (1999) On Minimum Stars, Minimum Steiner Stars, and Maximum Matchings.
Published In: Proceedings of the Fifteenth Annual Symposium on Computational Geometry : SCG '99 ; June 13- 16, 1999, Miami Beach, Florida ACM 1999, pp. 217-226.


We discuss properties and values of maximum matchings and minimum median problems for finite point sets. In particular, we consider ''minimum stars'', which are defined by a center chosen from the given point set, such that the total geometric distance |St| to all the points in the set is minimized. If the center point is not required to be an element of the set (i.e., the center may be a Steiner point), we get a ''minimum Steiner star'', of total length |StSt|. As a consequence of triangle inequality, the total length max|Mat| of any maximum matching is a lower bound for the length min|StSt| of a minimum Steiner star, which makes this ratio interesting in the context of optimal communication networks. The ratio also appears as the duality gap in an integer programming formulation of a location problem by Tamir and Mitchell. In this paper, we show that for an even set of points in the plane and Euclidean distances, the ratio min|StSt|/max|Mat| cannot exceed 2/sqrt{3}. This proves a conjecture of Suri, who gave an example where this bound is achieved. For the case of Euclidean distances in two and three dimensions, we also prove upper and lower bounds for the maximal value of the ratios min|St|/min|StSt| and min|St|/max|Mat|. We give tight upper bounds for the case where distances are measured according to the Manhattan metric: We show that in three-dimensional space, min|StSt|/max|Mat| is bounded by 3/2, while in two-dimensional space min|StSt|=max|Mat|, extending some independent observations by Tamir and Mitchell. Finally, we show that min|St|/min|StSt| has a tight bound of 3/2 in the two-dimensional case, and of 5/3 in the three-dimensional case.

Download: [img] Postscript - Preprinted Version
Download (250kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr98-340
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:46
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/340