Diverse Non Crossing Matchings
Abstract
Joint work with Harshil Mittal and Sarasati Nanoti ⸱ To Appear at CCCG 2022
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. We introduce a notion of distance between non-crossing matchings, and investigate the complexity of the problem of finding matchings that are far apart with respect to this notion of distance.