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