Information Technology Reference
In-Depth Information
Fig. 2.
A non-crossing properly colored geometric spanning 3-tree (Color figure online).
By our Theorem
1.2
, there exists a non-crossing properly colored geometric per-
fect matching
M
on
X
. By applying Theorem
1.5
to
M
, we can augment
M
into a non-crossing properly colored geometric spanning 3-tree on
X
. Note that
if
is not a perfect matching (one
isolated vertex remains), so we cannot apply Theorem
1.5
to
|X|
is odd, then a maximum matching
M
on
X
M
. In Sect.
4
,we
present another proof of Theorem
1.4
for both even and odd
.
We can also consider problems on red and blue points in the plane lattice
by using
|X|
-line segment
in
the plane lattice consists of a vertical line segment and a horizontal line segment
having a common endpoint. Kano et al. [
4
] proved the following theorem.
L
-line segments instead of line segments, where an
L
Theorem 1.6 (Kano and Suzuki
[
4
]
).
Let
be sets of red and blue
points in the plane lattice, respectively. Assume that every vertical line and hor-
izontal line passes through at most one point of the points. If
R
and
B
|R|
=
|B|
, then
there exists a non-crossing alternating geometric perfect matching on
R∪B
such
that each edge is an
L
-line segment.
Our third result is a generalization of this Theorem
1.6
for a 3-colored point set,
stated as Theorem
1.7
(Fig.
3
).
Theorem 1.7.
Let
be sets of red, blue, and green points in the plane
lattice, respectively. Assume that every vertical line and horizontal line passes
through at most one point of
R
,
B
,
G
X
=
R ∪ B ∪ G
.If
|X|
is even and each color
appears on at most
2
points, then there exists a non-crossing properly colored
geometric perfect matching on
|X|/
X
such that each edge is an
L
-line segment.
Fig. 3.
A non-crossing properly colored geometric perfect matching with
L
-line seg-
ments (Color figure online).
In order to prove our results, we propose the following lemma (Fig.
4
).
Search WWH ::
Custom Search