Properly Colored Geometric Matchings and 3-Trees Without Crossings on Multicolored Points in the Plane

摘要

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.