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
 
Search WWH ::




Custom Search