Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 11, 2018, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Miloš Stojaković (University of Novi Sad)
Given a set of n red and n blue points in the plane, we want to match red points with blue points by straight line segments so that the segments do not cross. Bottleneck matching is such a matching that minimizes the length of the longest segment. We develop a range of tools for dealing with non-crossing matchings of points in convex position, which enable us to solve the problem of finding bottleneck matchings of points in convex position in O(n2) time. Combining the same set of tools with a geometric analysis, we design an O(n)-time algorithm for the case where the given points lie on a circle. Joint work with Marko Savić.
Automatic MiSe System Software Version 1.4803M | admin login