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 edges such that each point of S is a vertex of exactly one edge. The weight of 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 depends 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 can 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 Science B.V. All rights reserved.
lower bounds minimum weight matching computational geometry