Information Technology Reference
In-Depth Information
For
n ≥
5, we suppose that the proposition holds for at most
n −
1 points.
The outline of the proof is that we will find a Spanning 3-Tree on
X − v
and
connect
and a point with degree at most 2 in the tree. We consider the following
two cases depending on the colors of the two neighbors of
v
v
of
conv
(
X
). By the
symmetry of the colors, we may assume that
v ∈ R
.
v
u
v
conv
X
Case 1.
and some neighbor vertex
of
of
(
)
have distinct colors,
u∈ R
namely,
.
|X − v|≥
4. By Claim
1
, for every
C ∈{R, B, G}
,
|C − v|≤|C|≤n/
2
−
1
≤
|X − v|/
2
points. Hence, since
u
is a vertex of
conv
(
X − v
), we can apply the
inductive hypothesis to
X − v
and
u
. Then there exists a Spanning 3-Tree
T
1
on
X − v
such that deg
T
1
(
u
) = 1. Therefore,
T
=
T
1
+
vu
is the desired Spanning
3-Tree on
X
.
Case 2.
v
and its two neighbor vertices of
conv
(
X
)
have the same color.
By a suitable rotation of the plane, we may assume that
v
is the highest vertex of
conv
(
X
), and
a
and
b
are the left and the right vertices of
conv
(
X
) adjacent to
v
,
respectively. We sort all the points of
X−v
with respect to their counterclockwise
angle from the ray emanating from
v
and passing through
a
, and denote the
sorted sequence by (
x
1
,x
2
,...,x
n−
1
) so that
x
1
=
a
and
x
n−
1
=
b
.
By Claim
1
, for every
C ∈{R, B, G}
,
|C −v|≤|C|≤n/
2
−
1
≤
(
n−
1)
/
2
points. Thus, in the sequence, each color appears on at most
|X − v|/
2
points.
The two end-points
x
n−
1
have the same color, namely red. Hence, by
Lemma
1.8
,thereexistsanevennumber
x
1
and
p
(2
≤ p ≤ n −
2) such that
x
p
∈ R
and for every
C ∈{R, B, G}
,
n −
|C ∩{x
1
,...,x
p
}| ≤
2
,
1
− p
|C ∩{x
p
+1
,...,x
n−
1
}| ≤
.
2
This implies that the line passing through
v
and
x
p
partitions
X \{v, x
p
}
into
Left
=
{x
1
(=
a
)
,x
2
,...,x
p−
1
}
and
Right
=
{x
p
+1
,...,x
n−
2
,x
n−
1
(=
b
)
}
as shown in Fig.
8
so that
a ∈ Left
,
b ∈ Right
,
|Left ∪{x
p
}|
=
p
,
|Right|
=
n −
1
− p
,andforevery
C ∈{R, B, G}
,
n −
|≤
2
,
1
− p
|C ∩
(
Left ∪{x
p
}
)
|C ∩ Right|≤
.
(3)
2
Here, we will find two Spanning 3-Trees
T
1
and
T
2
on
Left ∪{x
p
}
and
Right ∪{x
p
}
such that deg
T
1
(
x
p
) = 1 and deg
T
2
(
x
p
) = 1, respectively, and
connect the red point
v
to the non-red point
x
p
. By the symmetry of
B
and
G
,
we may assume that
.
First, we will find a Spanning 3-Tree
x
p
∈ B
T
1
on
Left∪{x
p
}
such that deg
T
1
(
x
p
)=
1. If
|Left ∪{x
p
}|
= 2 then the path
x
p
a
is the desired Spanning 3-Tree
T
1
.Thus,
since
p
is even, we suppose that
|Left ∪{x
p
}| ≥
4. Then, since
x
p
is a vertex of
conv
(
Left∪{x
p
}
), we can apply the inductive hypothesis to
Left∪{x
p
}
and
x
p
.
T
1
on
Left ∪{x
p
}
x
p
)=1.
Then there exists a Spanning 3-Tree
such that deg
T
1
(
Search WWH ::
Custom Search