1 of 14

DIVERSE NON-CROSSING MATCHINGS

CCCG 2022

Neeldhara Misra

Harshil Mittal

Saraswati Nanoti

2 of 14

PERFECT NON-CROSSING MATCHINGS

3 of 14

APPLICATION OF PERFECT NON-CROSSING MATCHINGS

  • Cranes and containers problem.
  • Each crane i must be assigned to a container j.
  • However, crane i can only be assigned to containers within a distance R from it and no two cranes may cross each other.
  • This is a Euclidean bipartite matching problem: given a collection of n red points (the cranes) and a collection of n blue points (the containers), our goal is to find a crossing-free matching between red-blue pairs. (bottleneck bichromatic matching).
  • Shape matching in pattern recognition.
  • VLSI design.
  • Computational Biology

John Gunnar Carlsson, Benjamin Armbruster, Haritha Bellam, and Rahul Saladi, A bottleneck matching problem with edge-crossing constraints (2015)

Ioannis Mantas, Mrko Savić, and Hendrik Schrezenmaier. New variants of Perfect Non-crossing Matchings (2021)

​

4 of 14

DISJOINT MATCHINGS

No edge is common to both the matchings.

5 of 14

COMPATIBLE MATCHINGS

Two perfect NCMs M and N are said to be compatible if no edge of M crosses any edge of N.

6 of 14

MONOCHROMATIC AND BICHROMATIC POINT SETS

7 of 14

FEASIBLE EDGE

(Bichromatic Points in Convex Position)

Endpoints are of opposite color and equal number of red and blue points between them.

8 of 14

EXISTENCE OF A PAIR OF MATCHINGS

9 of 14

COMPATIBLE MATCHINGS FOR MONOCHROMATIC POINTS IN GENERAL POSITION

10 of 14

DISJOINT MATCHINGS FOR BICHROMATIC POINTS IN CONVEX POSITION

11 of 14

DIVERSE NON-CROSSING MATCHINGS

  • Two solutions
  • Sufficiently “different” solutions !
  • Notion of “distance” between solutions.

​

 

 

12 of 14

ANOTHER DIVERSE NCM

For both monochromatic and bichromatic points in convex position, the problems ANOTHER DIVERSE NCM and ANOTHER DIVERSE COMPATIBLE NCM admit polynomial time algorithms.

13 of 14

DYNAMIC PROGRAMMING ALGORITHM

  • Finding locally optimal matchings N covering points on contiguous subintervals of points on the convex hull.

​

  • For any subproblem, we “guess” the matched partner of the extreme point on the subinterval under consideration.

​

  • Some choices of matched partners are clearly invalid.

​

  • For any legitimate choice, we naturally obtain at most two subproblems corresponding to points on either side of the guessed segment proposed as a part of the output matching.

14 of 14