Information Technology Reference
In-Depth Information
Next we consider the faces interior to
C
that share an edge or vertex with
C
.
We show that no such face collapses, provided that the weight distribution
w
satisfies
ʴ
1
=
ʴ
2
=
ʴ
3
where we use
ʴ
1
,
ʴ
2
and
ʴ
3
to denote
ʴ
1
(
yz
),
ʴ
2
(
xy
) and
ʴ
3
(
xz
) respectively.
Lemma 10.
Let
w
be a weight distribution for the interior faces of
T
such that
ʴ
1
=
ʴ
2
=
ʴ
3
.Nointeriorfaceof
T
|
C
incident to an exterior vertex of
T
|
C
ʓ,ʓ
collapses during
.
Proof sketch.
We examine separately the case where the interior face is incident
to the edge
xy
of
C
and the case where the interior face is only incident to the
vertex
x
of
C
. The other cases follow by analogous arguments.
Consider the case of an interior face
bxy
incident to edge
xy
. Suppose by
contradiction that at time
r
∈
[0
,
1] during the morph the face collapses with
b
r
lying on segment
x
r
y
r
,say
b
r
=(1
s
)
x
r
+
sy
r
[0
,
1].We
use formula (2) and Lemma 8 to re-write this equation. Some further algebraic
manipulations (details in the long version) show that there is no solution for
r
.
The case of a face involving vertex
x
and two interior vertices is similar.
−
for some
s
∈
We are now ready to prove the main result of this section.
Theorem 11.
Let
T
be a planar triangulation and let
S
and
S
be two Schny-
der woods of
T
such that
S
is obtained from
S
by flipping a counterclock-
wise cyclically oriented separating triangle
C
=
xyz
in
S
.Let
ʓ
and
ʓ
be
weighted Schnyder drawings obtained from
S
and
S
, respectively, with uniform
weight distribution. Then there exist weighted Schnyder drawings
ʓ
and
ʓ
on a
(6
n
−
15)
×
(6
n
−
15)
integer grid such that each of the following linear morphs
ʓ,ʓ
ʓ
,ʓ
ʓ,ʓ
,
,
and
is planar:
.
Proof.
Our aim is to define the planar drawings
ʓ
and
ʓ
. Each one will be
realized in a grid that is three times finer than the (2
n −
5)
×
(2
n −
5) grid,
i.e., in a (6
n−
15)
×
(6
n−
15) grid with weight distributions that sum to 6
n−
15.
Under this setup, the initial uniform weight distribution
u
takes a value of 3 in
each interior face.
Drawings
ʓ
and
ʓ
will be the weighted Schnyder drawings obtained from
S
and
S
respectively with a new weight distribution
w
.Weuse
Δ
1
,
Δ
2
and
Δ
3
to denote the regions
Δ
1
(
yz
),
Δ
2
(
xy
) and
Δ
3
(
xz
) respectively, in
S
.Weuse
ʴ
i
and
ʴ
i
to denote the weight of
Δ
i
,i
=1
,
2
,
3 with respect to the uniform weight
distribution and the new weight distribution
w
, respectively.
We will define
w
so that
ʴ
1
, ʴ
2
,
and
ʴ
3
all take on the average value
ʴ
:=
(
ʴ
1
+
ʴ
2
+
ʴ
3
)
/
3. The idea is to remove weight from faces in a region of above-
average weight, and add weight to faces in a region of below-average weight. The
new face weights must be positive integers. Note first that
ʴ
is an integer. Note
secondly that
ʴ>ʴ
i
/
3 for any
i
since the other
ʴ
j
's are positive. Thus
ʴ
i
−
ʴ<
3
ʴ
i
.
This means that we can reduce
ʴ
i
to the average
ʴ
without removing more than
2 weight units from any face (of initial weight 3) in any region. There is more
than one solution for
w
, but the morph might look best if
w
is as uniform as
