Bottleneck Bichromatic Non-crossing Matchings using Orbits.
Marko Savić, Miloš Stojaković · arXiv (Cornell University) · 2018
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 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(n^2)$ 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. Previously best known results were $O(n^3)$ for points in convex position, and $O(n \log n$) for points on a circle.