| On a Matching Problem in the Plane (2000) | |||||||||||||||
Abstract | |||||||||||||||
| 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, where w and b are even numbers. We show that there exists a matching of points of the same color with straight line segments and no crossings which matches at least 83:33% of the points. We also derive an O(n log n) algorithm which achieves this guarantee. On the other hand, there exist configurations of points such that any matching with the above properties matches at most 99:36% of the points. We also derive similar bounds on the number of matched points when the points are colored by a fixed number of colors. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||