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. 8.
A balanced partition and the desired Spanning 3-tree (Color figure online).
Next, we will find a Spanning 3-Tree
T
2
on
Right∪{x
p
}
such that deg
T
2
(
x
p
)=
1. If
|Right ∪{x
p
}|
= 2 then the path
x
p
b
is the desired Spanning 3-Tree
T
2
.If
|Right ∪{x
p
}|
= 3 then
n −
1
− p
=
|Right|
= 2. Thus, by the inequality (
3
),
|C ∩ Right|≤
1. Thus implies that
Right ∪{x
p
}
has one red point
b
, one blue
point
x
p
, and one blue or green point
g
. Hence, the path
x
p
bg
is the desired
Spanning 3-Tree
T
2
.
Thus, we suppose that
|Right ∪{x
p
}| ≥
4. If for every
C ∈{R, B, G}
,
|C ∩
(
Right ∪{x
p
}
)
|≤
(
n − p
)
/
2
, then, since
x
p
is a vertex of
conv
(
Right ∪
{x
p
}
), we can apply the inductive hypothesis to
Right∪{x
p
}
and
x
p
. Then there
exists a Spanning 3-Tree
T
2
on
Right ∪{x
p
}
such that deg
T
2
(
x
p
)=1.
Hence, we suppose that for some
C ∈{R, B, G}
,
|C ∩
(
Right ∪{x
p
}
)
| >
(
n − p
)
/
2
. Since
x
p
is blue, by the inequality (
3
), we have
n − p
2
n −
+1=
n − p
1
− p
+1
< |B ∩
(
Right ∪{x
p
}
)
|≤
.
2
2
This implies that
n − p
is even and
|B ∩
(
Right ∪{x
p
}
)
|
=(
n − p
)
/
2 + 1. Set
W
=
B ∩
(
Right ∪{x
p
}
)and
K
=(
Right ∪{x
p
}
)
\ W
. Then,
(
n − p
2
+1)=
n − p
2
|K|
=
|Right ∪{x
p
}| − |W|
=(
n −
1
− p
+1)
−
−
1
Thus,
|W|
=
|K|
+ 2. Hence, since
x
p
∈ W
is a vertex of
conv
(
W ∪ K
), we can
apply Proposition
4.1
to
W
,
K
,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
.
5 Proof of Theorem
1.7
by Using Lemma
1.8
We can prove Theorem
1.7
in the same way as the proof of Theorem
1.2
in Sect. 3.
We briefly call a non-crossing properly colored geometric perfect matching (such
that each edge is an
L
-line segment)
a Perfect Matching
. Set 2
n
=
|X|
.Weprove
the theorem by induction on
n
.If
n
= 1 then the theorem is true. For
n ≥
2, we
suppose that the theorem holds for 2(
n −
1) points.
Suppose that
|C|
=
n
for some
C ∈{R, B, G}
. Set
W
=
C
and
K
=
R ∪ B ∪ G
\ C
W
(
)
. We recolor all the points of
with white, and all the points
Search WWH ::
Custom Search