Matching colored points in the plane: Some new results

Let S be a set with n = w + b points in general position in the plane, w of them white, and b of them black. We consider the problem of computing G(S) , a largest non-crossing matching of pairs of points of the same color, usi ng straight line segments. We present two new algorithms which compute a la rge matching, with an improved guarantee in the number of matched points. T he first one runs in O(n(2)) time and finds a matching of a least 85.71% of the points. The second algorithm runs in O(n log n) time and achieves a pe rformance guarantee as close as we want to that of the first algorithm. On the other hand, we show that there exist configurations of points such that any matching with the above properties matches fewer than 98.95% of the po ints. We further extend these results to point sets with a prescribed ratio of the sizes of the two color classes. In the end, we discuss the more gen eral problem when the points are colored with any fixed number of colors. ( C) 2001 Elsevier Science B.V. All rights reserved.