Properly Colored Geometric Matchings and 3-Trees Without Crossings on Multicolored Points in the Plane - Discrete and Computational Geometry and Graphs - page 99

Lemma 1.8. Let ( x 1 ,x 2 ,...,x n ) be a sequence of n ≥ 3 points colored with 3

colors, say red, blue, and green. Let be sets of red, blue, and green points

in the sequence, respectively. Assume that the both ends

R , B , G

x 1 and x n have the same

color. If each color appears on at most n/ 2 points, then there exists an even

number p (2 ≤ p ≤ n − 1) such that x p and x 1 have distinct colors and for every

C ∈{R, B, G} ,

|C ∩{x 1 ,...,x p }| ≤ 2 ,

n − p
2

|C ∩{x p +1 ,...,x n }| ≤ .

x x p x n

1

Fig. 4. Example of Lemma 1.8 (Color figure online).

This lemma gives a balanced partition of a 3-colored sequence, in the sense that
every color appears on at most half of the points in each part of the partition.
In our inductive proofs, this lemma is useful in some cases where some “ends”
have the same color. We expect applications of the Lemma to problems where
each color appears on at most half of points.
We can generalize above our results for a multicolored point set with 2, 3 or
more colors, by using the following lemma.

N X = {n 1 ,n 2 ,...,n r } r ≥

Lemma 1.9. Let ( 4) be a set of positive integers.

Set n = n 1 + n 2 + ··· + n r .Ifeachinteger n i is at most n/ 2 then there exists

a tripartition N X = N R ∪ N B ∪ N G such that

2 2 2

k ≤ , k ≤ , k ≤ .

k ∈ N R k ∈ N B k ∈ N G

Proof. We may assume that n 1 ≤ n 2 ≤ ··· ≤n r . Then n 1 ≤n/r≤n/ 4 <

n/ r ≥ n ≥ n j , it follows that n 1 + n 2 +

2 since 4and 4. Thus, for some integer

··· n j < n/ n 1 + n 2 + ··· n j + n j +1 ≥n/ n j +2 + n j +3 +

+ 2 and + 2 . Then,

··· + n r = n − ( n 1 + n 2 + ··· + n j + n j +1 ) ≤ n −n/ 2 = n/ 2 . Note that

1 ≤ j ≤ r − 2 because if j = r − 1 then n r = n − ( n 1 + ··· + n j ) >n−n/ 2 =

n/ 2 , which contradicts our assumption. Hence, we have the desired tripartition

N R = {n 1 ,...,n j } , N B = {n j +1 } ,and N G = {n j +2 ,...,n r } .

By using Lemma 1.9 , where let ,wecan

obtain the following results for multicolored points from Theorems 1.2 , 1.4 , 1.7 ,
and Lemma 1.8 .

n i be the number of points of color i