Bichromatic compatible matchings

Luis Barba

For a set R of n red points and a set B of n blue points, a BR-matching is a non-crossing geometric perfect matching where each segment has one endpoint in B and one in R. Two BR-matchings are compatible if their union is also non-crossing. We prove that, for any two distinct BR-matchings M and M', there exists a sequence of BR-matchings M = M1 ,..., Mk = M' such that Mi-1 is compatible with Mi. This implies the connectivity of the compatible bichromatic matching graph containing one node for each BR-matching and an edge joining each pair of compatible BR-matchings.