Diverse Non Crossing Matchings*

A perfect matching M on a set P of n points is a collection of line segments with endpoints from P such that every point belongs to exactly one segment. A matching is non-crossing if the line segments do not cross. Two matchings M and N are said to be compatible if there are no crossings among any pair of line segments in M ∀ N. We introduce a notion of diverse non-crossing matchings: a pair of perfect matchings M and N are k-diverse if, for every p ? P, the distance between the matched partners of p in M and N is at least k. In this contribution, we describe a polynomial time algorithm to determine if a set of points in convex position admits two compatible and perfect NCMs that are k-diverse. For points in convex position, we also show that if a perfect matching M is given as input, then we can determine, in polynomial time, if another perfect matching N exists that is compatible with M and is such that M and N are k-diverse. Finally, we also establish that every point set in general position admits a pair of compatible and perfect NCMs. The first two results also hold for bichromatic points, and we also give a characterization for when a bichromatic point set in convex position admits a pair of perfect and disjoint NCMs.