Dealing with bichromatic non-crossing matchings

Abstract: Given a set of n red and n blue points in the plane, we are interested in matching red points with blue points by straight line segments so that the segments do not cross. We develop a range of tools for dealing with the non-crossing matchings of points in convex position. It turns out that the points naturally partition into groups that we refer to as orbits, with a number of properties that prove useful for studying and efficiently processing the non-crossing matchings.

Bottleneck matching is such a matching that minimizes the length of the longest segment. Illustrating the use of the developed tools, we show how to solve the problem of finding bottleneck matchings of points in convex position faster than before.

Joint work with Marko Savić.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456