On the intersection number of matchings and minimum weight perfect matchings of multicolored point sets

Let P and Q be disjoint point sets with 2r and 2s elements respectively, and M 1 and M 2 be their minimum weight perfect matchings (with respect to edge lengths). We prove that the edges of M 1 and M 2 intersect at most |M 1|%2b|M 2|-1 times. This bound is tight. We also prove that P and Q have perfect matchings (not necessarily of minimum weight) such that their edges intersect at most min{r,s} times. This bound is also sharp. © Springer-Verlag 2005.

VIVO