Quasi-parallel segments and characterization of unique bichromatic matchings
Andrei Asinowski, Tillmann Miltzow, Günter Rote · Journal of Computational Geometry (Carleton University) · 2013
Given n red and n blue points in general position in the plane, it is well-known that there is a perfect matching formed by non-crossing line segments. We characterize the bichromatic point sets which admit exactly one non-crossing matching. We give several geometric descriptions of such sets, and find an O(n log n) algorithm that checks whether a given bichromatic set has this property.