• 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