Given a set S of n red points and n blue points in the plane, a (non-crossing geometric bichromatic perfect) matching consists of n pairwise-disjoint straight-line segments, each of which has a red endpoint and a blue endpoint. Two such matchings are considered to be neighbors if their union does not strictly intersect. We consider a graph G in which every vertex corresponds to a matching of S. If two matchings are neighbors, then they share an edge in G. We show that for every set S its corresponding graph G is connected.
Time permitting, we will discuss bounds on the diameter of G, and will mention similar results about matching of non-colorful point sets.
Joint work with Luis Barba, Stefan Langerman, and Diane Souvaine.