Information Technology Reference
In-Depth Information
3.
D
1
(
x
)=
D
1
(
x
)
,
D
2
(
z
)=
D
2
(
z
)
and
D
3
(
y
)=
D
3
(
y
)
.
4. The interiors of
R
1
(
x
)
,
R
2
(
z
)
and
R
3
(
y
)
are pairwise disjoint.
5.
D
1
(
x
)
is contained in the interior of
R
1
(
x
)
and similarly for
y
and
z
.
Consequently
D
1
(
x
)
,
D
2
(
z
)
and
D
3
(
y
)
are pairwise disjoint.
\{
x
}
a
1
a
1
a
1
a
1
ʔ
1
(
yz
)
ʔ
1
(
yz
)
D
2
(
y
)
D
3
(
y
)
D
2
(
y
)
D
3
(
y
)
S
S
y
z
f
ʔ
3
(
xz
)
ʔ
2
(
xy
)
ʔ
3
(
xz
)
ʔ
2
(
xy
)
f
x
x
z
y
a
3
a
3
a
2
a
2
a
3
a
3
a
2
a
2
D
1
(
x
)
D
1
(
x
)
Fig. 3. A flip of a counterclockwise oriented face triangle
xyz
showing changes to the
regions. Observe that
ʔ
1
(
yz
)
∪{f}
leaves
R
2
(
x
) and joins
R
3
(
x
).
Next we study the difference between the coordinates of the weighted Schny-
der drawings corresponding to
S
and
S
.
Lemma 6.
For each
v
∈
V
(
T
)
,
⊧
⊨
(
v
1
,v
2
,v
3
)
if
v
∈
D
1
(
x
)
∪
D
2
(
z
)
∪
D
3
(
y
)
(
v
1
,v
2
−
(
ʴ
1
(
yz
)+
w
(
f
))
,v
3
+
ʴ
1
(
yz
)+
w
(
f
))
if
v
∈
D
1
(
x
)
(
v
1
,v
2
,v
3
)=
⊩
(
v
1
+
ʴ
2
(
xy
)+
w
(
f
)
,v
2
,v
3
−
(
ʴ
2
(
xy
)+
w
(
f
)))
if
v
∈
D
2
(
z
)
(
v
1
−
(
ʴ
3
(
xz
)+
w
(
f
))
,v
2
+
ʴ
3
(
xz
)+
w
(
f
)
,v
3
)
if
v
∈
D
3
(
y
)
.
We are ready to prove the main result of this section. We express it in terms
of a general weight distribution since we will need that in the next section.
Theorem 7.
Let
S
be a Schnyder wood of a planar triangulation
T
that contains
aface
f
bounded by a counterclockwise directed triangle
xyz
,andlet
S
be the
Schnyder wood obtained from
S
by flipping
f
.Denoteby
ʓ
and
ʓ
the weighted
Schnyder drawings obtained from
S
and
S
respectively with weight distribution
ʓ,ʓ
w
.Then
is a planar morph.
Proof.
If a triangle collapses during the morph, then it must be incident to at least
one vertex that moves, i.e., one of
D
1
(
x
)
,D
2
(
y
) or
D
3
(
z
). By Lemma 5, apart from
x, y, z
these vertex sets lie in the interiors of regions
R
1
(
x
)
,R
2
(
y
)
,R
3
(
z
) respec-
tively. Thus it suces to show that no triangle in one of these regions collapses,
and that no triangle incident to
x, y
or
z
collapses.
Let
t
be a triangle such that
t
R
1
(
x
). (The argument for triangles in other
regions is similar.) Any vertex of
R
1
(
x
) that moves is in
D
1
(
x
) and by Lemma 6
∈