Combinatorics Seminar - Miloš Stojakovic
Speaker: Miloš Stojakovic
Title: 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.
Joint work with Marko Savić.