Information Technology Reference
In-Depth Information
Corollary 1.10. Let
be a set of multicolored points in the plane such that
no three points are collinear. If
X
|X|
is even and each color appears on at most
|X|/
2 points, then there exists a non-crossing properly colored geometric perfect
matching on
.
Corollary 1.11. Let
X
X
be a set of multicolored points in the plane such that no
three points are collinear. If each color appears on at most
|X|/
points, then
there exists a non-crossing properly colored geometric spanning 3 -trees on
2
X
.
Corollary 1.12. Let
be a set of multicolored points in the plane lattice.
Assume that every vertical line and horizontal line passes through at most one
point of
X
2 points, then
there exists a non-crossing properly colored geometric perfect matching on
X
.If
|X|
is even and each color appears on at most
|X|/
X
L
such that each edge is an
-line segment.
Corollary 1.13. Let (
x 1 ,x 2 ,...,x n ) be a sequence of multicolored
n ≥
3 points.
For each color
j
,let
C j be a set of points colored with
j
in the sequence. Assume
that the both ends
x 1 and
x n have the same color. If
|C j |≤n/
2
for every color
j
, then there exists an even number
p
(2
≤ p ≤ n −
1) such that
x p and
x 1 have
j
distinct colors and for every color
,
|C j ∩{x 1 ,...,x p }| ≤ 2 ,
n − p
2
|C j ∩{x p +1 ,...,x n }| ≤
.
In this paper, we will prove Lemma 1.8 , Theorem 1.2 , Theorem 1.4 , and Theorem
1.7 in Sects. 2 , 3 , 4 ,and 5 , respectively.
Throughout this paper, we will use the following definitions, notations, and
a fact. For two points
x
and
y
in the plane,
xy
denotes the line segment joining
x
and
y
.Foraset
X
of points in the plane, we denote by
conv
(
X
) the boundary
of the convex hull of
X
. We call a point in
X ∩ conv
(
X
)a vertex of
conv
(
X
).
For a graph
G
and its vertex
v
, we denote by deg G (
v
) the degree of
v
in
G
.For
positive integers
n
,
a
,and
b
such that
n
=
a
+
b
, we know that
a ≤n/
2
and
b ≤n/
2
if and only if
|a − b|≤
1. It is also known that
n/
2
+
n/
2
=
n
.We
often use these facts without mentioning.
2 Proof of Lemma 1.8
By the symmetry of the colors, we may assume that
x 1 and
x n are red. First,
we claim the lemma holds when
B
=
or
G
=
,say
G
=
.
Claim 1. If
G
=
then there exists an even number
p
(2
≤ p ≤ n −
1) such
that
x p is blue and
= 2 ,
|R ∩{x 1 ,...,x p }|
=
|B ∩{x 1 ,...,x p }|
n − p
2
n − p
2
|R ∩{x p +1 ,...,x n }| ≤
, |B ∩{x p +1 ,...,x n }| ≤
.
 
Search WWH ::




Custom Search