| Title | : | Diverse Pair of Compatible Non-Crossing Matchings for Points in Convex Position |
| Speaker | : | Harshil Mittal (IIT Madras) |
| Details | : | Tue, Jul 22, 2025 4:00 PM, @ Turing Hall (SSB 334) |
| Abstract | : | Consider a set P of an even number of points on a plane. A 'perfect matching’ M of P is a collection of line segments with endpoints in P such that every point of P is the endpoint of exactly one segment in M. Also, M is said to be a ‘non-crossing matching’ (NCM) if no two of its segments cross each other. Two perfect NCMs of P are said to be 'compatible' with each other if no segment of one matching crosses a segment of the other matching. It is known that a pair of compatible perfect NCMs always exists and can be found in polynomial time. In this talk, we shall explore this setting in the framework of 'diversity', where the goal is to find 'diverse solutions', i.e., multiple solutions that are maximally far-apart/dissimilar from each other. To this end, we shall introduce a notion of distance between matchings, and then devise a polynomial-time algorithm to compute a 'diverse pair' of (i.e., a pair of maximally far-apart) compatible perfect NCMs when points of P are in convex position. We shall also discuss a polynomial-time algorithm for the related setting wherein apart from the point set P (again, in convex position), a base matching M of P is also given as input, and the goal is to find a perfect NCM of P that is maximally far apart from M. This work is based on joint discussions with Neeldhara Misra and Saraswati Girish Nanoti from IIT Gandhinagar. |