Let @math and @math be sets of @math red and @math blue points in the plane, respectively, with @math . Let @math be a perfect matching between points from @math and @math , using @math straight line segments to match the points, that is, each point is an endpoint of exactly one line segment, and each line segment has one red and one blue endpoint. We forbid line segments to cross. Denote the length of a longest line segment in @math with @math , which we also call the [ ] value, bn of @math . We aim to find a matching under given constraints that minimizes @math . Any such matching is called a [ ] bottleneck matching of @math .
A variant of the bichromatic case is the so-called bicolored (or multicolored, when there are arbitrary many colors) case, where only the points of the same color are allowed to be matched. Abu-Affash, Bhore and Carmi in @cite_12 examined bicolored matchings that minimize the number of crossings between edges matching different color sets. They presented an algorithm to compute a bottleneck matching of points in convex position among all matchings that have no crossings of this kind.
@cite_12
2951895579
Let (X ) be a set of multicolored points in the plane such that no three points are collinear and each color appears on at most ( |X| 2 ) points. We show the existence of a non-crossing properly colored geometric perfect matching on (X ) (if (|X| ) is even), and the existence of a non-crossing properly colored geometric spanning tree with maximum degree at most (3 ) on (X ). Moreover, we show the existence of a non-crossing properly colored geometric perfect matching in the plane lattice. In order to prove these our results, we propose an useful lemma that gives a good partition of a sequence of multicolored points.