Andrei Asinowski, Tillmann Miltzow, and Günter Rote:

Quasi-parallel segments and characterization of unique bichromatic matchings

  1. Extended abstract. In: Abstracts of the 29th European Workshop on Computational Geometry (EuroCG'13), Braunschweig, March 2013, Editor: Sándor Fekete, pp. 225–228.
  2. Journal of Computational Geometry 6 (2015), 185–219. arXiv:1302.4400 [cs.CG].


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.

  pdf file (gzipped)
other papers about this subject
Last update: July 19, 2013.