Title of article
On a matching problem in the plane
Author/Authors
Adrian Dumitrescu، نويسنده , , William Steiger، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2000
Pages
13
From page
183
To page
195
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.
Journal title
Discrete Mathematics
Serial Year
2000
Journal title
Discrete Mathematics
Record number
950293
Link To Document