A lower bound for approximating the geometric minimum weight matching

Given a set S of 2n points in R-d, a perfect matching of S is a set of n ed ges such that each point of S is a vertex of exactly one edge. The weight o f a perfect matching is the sum of the Euclidean lengths of all edges. Rao and Smith have recently shown that there is a constant r > 1, that only dep ends on the dimension d, such that a perfect matching whose weight is less than or equal to r times the weight of a minimum weight perfect matching ca n be computed in O(n log n) time. We show that this algorithm is optimal in the algebraic computation tree model. (C) 2000 Published by Elsevier Scien ce B.V. All rights reserved.