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