Information Technology Reference
In-Depth Information
v
v
x
n
-1
=
b
x
1
=
a
x
2
T
2
x
3
T
x
5
1
x
p
x
p
x
4
Fig. 6.
A balanced partition and the desired Spanning 3-tree (Color figure online).
conditions (i), (ii), or (iii) holds: (i)
|W|
=1,1
≤|K|≤
3, and
x
p
∈ K
,
(ii) 2
≤|W|
,
|K|
=
|W|
+2, and
x
p
∈ K
, (iii) 2
≤|W|≤|K|≤|W|
+ 1. 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
2
on
Right ∪{x
p
}
such
that deg
T
2
(
x
p
)=1.
Consequently,
T
=
T
1
+
T
2
+
vx
p
is the desired Spanning 3-tree on
X
.
Subcase 2.2.
v, a, b ∈ B
.
We sort all the points of
X
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
) so that
x
1
=
v
,
x
2
=
a
,and
x
n
=
b
. Note that in this subcase
R
and
B
satisfy Condition (iii) since
v ∈ B
, that is, 2
≤|B|≤|R|≤|B|
+1.
Thus, in the sequence, each color appears on at most
n/
2
points. Since the
two end-points
x
n
have the same color, namely blue, by Lemma
1.8
,
thereexistsanevennumber
x
1
and
p
(2
≤ p ≤ n −
1) such that
x
p
∈ R
and for every
C ∈{R, B}
,
n − p
2
|C ∩{x
1
,...,x
p
}| ≤
2
,
|C ∩{x
p
+1
,...,x
n
}| ≤
.
This implies that the line passing through
v
and
x
p
partitions
X \{v, x
p
}
into
Left
=
{x
2
(=
a
)
,x
3
,...,x
p−
1
}
and
Right
=
{x
p
+1
,...,x
n−
1
,x
n
(=
b
)
}
as shown in Fig.
7
so that
a ∈ Left
,
b ∈ Right
,
|Left ∪{x
1
(=
v
)
,x
p
}|
=
p
,
|Right|
=
n − p
,andforevery
C ∈{R, B}
,
n − p
2
|≤
2
,
|C ∩
(
Left ∪{v, x
p
}
)
|C ∩ Right|≤
.
(2)
T
1
and
T
2
on
Left ∪{x
p
}
Here, we will find two Spanning 3-Trees
and
Right ∪{x
p
}
such that deg
T
1
(
x
p
) = 1 and deg
T
2
(
x
p
) = 1, respectively, and
connect the blue point
v
to the red point
x
p
.
First, set
W
=(
R∩Left
)
∪{x
p
}
and
K
=
B∩Left
. Since
Left∪{x
1
(=
v
)
,x
p
}
has even points and
x
1
(=
v
) is blue,
|W|
=
|K|
+ 1. Hence, since
x
p
∈ W
is a
vertex of
conv
(
W ∪K
), we can apply the inductive hypothesis to
W
,
K
,and
x
p
.
Then there exists a Spanning 3-Tree
T
1
on
Left ∪{x
p
}
such that deg
T
1
(
x
p
)=1.
Search WWH ::
Custom Search