Information Technology Reference
In-Depth Information
Subcase 1.3.
Condition (iii) holds and
v ∈ B
.
If
|B|
= 2 then 2
≤|R|≤
3and
|B − v|
= 1. Thus, since
u ∈ R
,
R
and
B − v
satisfy Condition (i). If 3
≤|B|
then 2
≤|B − v|
. By Condition (iii), we have
2
≤|B − v|≤|B|≤|R|≤|B|
+1 =
|B − v|
+ 2. Thus, since
u ∈ R
,
R
and
B − v
satisfy Condition (ii) or (iii). Hence, since
u
is a vertex of
conv
(
X − v
), we can
apply the inductive hypothesis to
R
,
B − v
,and
u
. Then there exists a Spanning
3-Tree
T
1
on
R ∪
(
B − 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.
Subcase 2.1.
v, a, b ∈ R
.
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
x
1
,x
2
,...,x
n−
1
) so that
x
1
=
a
x
n−
1
=
b
≤|B|≤|R|≤|B|
by (
and
. Since 2
+2,
≤|B|−
≤|R − v|≤|B|
||R − v|−|B|| ≤
we have 1
1
+ 1, which implies
1.
Thus, in the sequence, each color appears on at most
(
n −
1)
/
2
points. Since
the two end-points
x
n−
1
have the same color, namely red, by Lemma
1.8
,
there exists an even number
x
1
and
p
(2
≤ p ≤ n −
2) such that
x
p
∈ B
and for every
C ∈{R, B}
,
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.
6
so that
a ∈ Left
,
b ∈ Right
,
|Left ∪{x
p
}|
=
p
,
|Right|
=
n −
− p
C ∈{R, B}
1
,andforevery
,
n −
|≤
2
,
− p
1
|C ∩
(
Left ∪{x
p
}
)
|C ∩ Right|≤
.
(1)
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 blue point
x
p
.
First, set
W
=
R ∩ Left
and
K
=(
B ∩ Left
)
∪{x
p
}
. Since
p
is even,
|K|
=
|W|
. Hence, since
x
p
∈ K
is a vertex of
conv
(
K ∪ W
), we can apply the
inductive hypothesis to
K
,
W
,and
x
p
. Then there exists a Spanning 3-Tree
T
1
on
Left ∪{x
p
}
such that deg
T
1
(
x
p
)=1.
Next, set
W
=
R ∩ Right
and
K
=(
B ∩ Right
)
∪{x
p
}
. By the inequality
(
1
),
||W|−
(
|K|−
1)
|
=
||R ∩ Right|−|B ∩ Right|| ≤
1. Thus, we have
−
1
≤
|W|−
|K|−
≤
≤|K|−|W|≤
(
1)
1, that is, 0
2. Then, either of the following
Search WWH ::
Custom Search