Information Technology Reference
In-Depth Information
these vertices are all translated by the same amount. We argue that if triangle
b,c,e
in clockwise order collapses as we translate a subset of its vertices then
the end result is triangle
b,c,e
in counterclockwise order. This contradicts the
fact that
ʓ
and
ʓ
have the same faces. A rigorous proof is in the long version.
The same argument applies to a triangle in
Δ
3
(
xz
)
∪
Δ
2
(
xy
) that is incident to
x
but not incident to either
y
or
z
.
It remains to prove that no triangle
t
incident to at least two vertices of
x, y
and
z
collapses. Here we only consider the case where
t
=
xyz
, the other case
can be handled similarly. We will show that
x
never lies on the line segment
yz
during the morph. (The other two cases are similar.) Since (
x, y
) has colour 1
in
S
, it follows that
x
∈
R
1
(
y
). Similarly, since (
z,x
) has colour 2 in
S
,wehave
R
1
(
z
). Therefore
x
1
<y
1
,z
1
. Using a similar argument on
S
we obtain
that
x
1
<y
1
,z
1
. Finally, note that
x
1
=
x
1
. This implies that
x
never lies on
the line segment
yz
during the morph.
that
x
∈
6 Morphing to Flip a Separating Triangle
In this section we prove that there is a planar morph between any two weighted
Schnyder drawings that differ by a separating triangle flip. Our morph will be
composed of three linear morphs. Throughout this section we let
S
and
S
be
Schnyder woods of a planar triangulation
T
such that
S
is obtained from
S
after
flipping a counterclockwise oriented separating triangle
C
=
xyz
,with(
x, y
)
coloured 1 in
S
.Let
ʓ
and
ʓ
be two weighted Schnyder drawings obtained
from
S
and
S
respectively with weight distribution
w
. For the main result of
the section, it suces to consider a uniform weight distribution because we can
get to it via a single planar linear morph, as shown in Section 4. However, for the
intermediate results of the section we need more general weight distributions.
We now give an outline of the strategy we follow. Morphing linearly from
ʓ
to
ʓ
may cause faces inside
C
to collapse. An example is provided in the long
version. However, we can show that there is a “nice” weight distribution that
prevents this from happening. Our plan, therefore, is to morph linearly from
ʓ
toadrawing
ʓ
with a nice weight distribution, then morph linearly to drawing
ʓ
to effect the separating triangle flip. A final change of weights back to the
uniform distribution gives a linear morph from
ʓ
to
ʓ
.
This section is structured as follows. First we study how the coordinates
change between
ʓ
and
ʓ
. Next we show that faces strictly interior to
T|
C
do not collapse during a linear morph between
ʓ
and
ʓ
. We then give a similar
result for faces of
T
|
C
that share a vertex or edge with
C
provided that
the
weight distribution satisfies certain properties. Finally we prove the main result
by showing that there is a weight distribution with the required properties.
Let us begin by examining the coordinates of vertices. For vertex
b
V
(
T
)
let (
b
1
,b
2
,b
3
) and (
b
1
,b
2
,b
3
) denote its coordinates in
ʓ
and
ʓ
respectively.
For
b
an interior vertex of
T
∈
|
C
let
ʲ
i
be the
i
-th coordinate of
b
in
T
|
C
when
considering the restriction of
S
to
T
|
C
with weight distribution
w
. By analyzing
