University of Novi Sad
Tuesday, April 17 at 3:00 PM
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. Bottleneck matching is such a matching that minimizes the length of the longest segment. We develop tools which enable us to solve the problem of finding bottleneck matchings of points in convex position in $O(n^2)$ time. We use the same tools to design an $O(n)$-time algorithm for the case where all points lie on a circle. Previously best known results were $O(n^3)$ for points in convex position, and $O(n \log n$) for points on a circle.