Connectivity of Bichromatic Matchings

Greg Aloupis, New York University

March 6, 2018

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.