Game Development Reference
In-Depth Information
T is a search tree. We have to
clear ( v )
search ( f )=
and therefore
show that it is tighter than
T
. Clearly, the weight of all nodes v
= t remains
unchanged. Furthermore, we get
δ clear ( t ) , search ( e 1 ) ,...,search ( e r )
|
guard ( t )
|
=
|
V [ new ( t )]
|
(7.1)
δ ( new ( t ) , clear ( t ) , search ( e 1 ) ,...,search ( e r )
V [ new ( t )]
=
|
δ ( new ( t )) |
\
(7.2)
δ ( new ( t ) , clear ( t ) , search ( e 1 ) ,...,search ( e r ) |
=
|
+
| V [ new ( t )]
δ ( new ( t )) |
\
(7.3)
new ( t ) ( clear ( t ) , search ( e 1 ) ,...,search ( e r ) |
≥|
+
| V [ new ( t )]
search ( e ) |
search ( e )
\
δ ( new ( t ))
(7.4)
= ( clear ( t ) , search ( e 1 ) ,...,search ( e r )
V [ new ( t )] ∩ search ( e ) |
= |guard ( t ) |.
The equality between (7.1) and (7.2) follows from the fact that V [ new ( t )]
δ ( new ( t ) , clear ( t ) , search ( e 1 ) ,...,search ( e r ) = δ ( new ( t )). The equality of
(7.2) and (7.3) then follows as the two sets are disjoint by construction. The
inequality in (7.4) follows from Lemma 7.23 above.
If ( search ( e )) | > |δ ( clear ( e )) | then the inequality in (7.4) is strict and
therefore in this case we get w T ( t ) <w T ( t ) and therefore weight ( T ) <
weight ( T ).
Otherwise, if
then the inequality in (7.4) may
not be strict and we therefore only get that w T ( t ) ≤ w T ( t ) and therefore
weight ( T ) ≤ weight ( T ). However, in this case the edge e is now monotone, by
construction, and the only edges which may now have become non-monotone
are e 1 ,...,e r whose distance from the root is larger than the distance of e
from the root. Therefore, the badness of
|
δ ( search ( e ))
|
=
|
δ ( clear ( e ))
|
T is less than the badness of
T
.
.
Case 2. Now assume ( search ( e )) | > |δ ( clear ( e )) | and let e 1 ,...,e r be
the out-going edges of s other than e . We define a new search tree T :=
( T,new , search ) where new ( v ):= new ( v ) , clear ( v ):= clear ( v ) for all v = t
and search ( f )= search ( f ) for all f = e and
This concludes the first case where
|
δ ( search ( e ))
|≤|
δ ( clear ( e ))
|
search ( e ):= E ( G )
\
clear ( t )
new ( s ):= new ( s )
clear ( t )
search ( e i ):= search ( e i )
clear ( t )
for all 1
i
r
clear ( s ):= clear ( s )
clear ( t ) .