Andrei Asinowski, Tillmann Miltzow, and Günter Rote:
Quasi-parallel segments and characterization of unique bichromatic
matchings
-
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
-
Journal of Computational Geometry 6 (2015),
185–219.
doi:10.20382/jocg.v6i1a8, arXiv:1302.4400 [cs.CG].
→BibTeX
Abstract
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.
Last update: November 29, 2019.