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.  →BibTeX
  2. Journal of Computational Geometry 6 (2015), 185–219. doi:10.20382/jocg.v6i1a8, arXiv:1302.4400 [cs.CG].  →BibTeX


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
other papers about this subject
Last update: November 29, 2019.