Information Technology Reference
In-Depth Information
e 1
x 1
x 2
x j− 1
x 3
x j = y k
f 1
f 2
f 0
f j− 1
y 1
y 2
y j− 1
y 3
y j
e 2
Fig. 2. If x j = y k ,then e 2 crosses itself
7 such that f k
is not a 0-quadrilateral (notice that if f i is not a 0-quadrilateral, then f i +1 is
not defined). We say that f k is the distant neighbor of f 0 at [ x 1 y 1 ], and that the
M -edge [ x k y k ] is the edge of f k that faces [ x 1 y 1 ]. Note that x k and y k must be
crossing points, since they belong to the 0-quadrilateral f k− 1 or coincide with x 1
and y 1 ,if k = 1. It is also important to note that if f 0 is not a 0-quadrilateral,
then f 0 is the distant neighbor of f k at [ x k y k ]and[ x 1 y 1 ] is the edge of f 0 that
faces [ x k y k ]. Indeed, this follows from the definition of a distant neighbor and
from the fact that the relation immediate neighbor at a certain M -edge and the
relation opposite edge in a 0-quadrilateral are one-to-one.
k
seven crossing points. Therefore there must be an index 1
Proposition 2. Let t be a 0 -or 1 -triangle whose vertices are x, y and z,such
that x and y are crossing points in D,andlete 1 (resp., e 2 )betheD-edge that
contains [ zx ] (resp., [ zy ] ). Suppose that f is the distant neighbor of t at [ xy ] and
e istheedgeoff that faces [ xy ] .Then:
1. the endpoints of e are crossing points in D;
2. one endpoint of e (denote it by p)liesone 1 and the other endpoint of e
(denote it by q)liesone 2 ;
3. t is the distant neighbor of f at [ pq ] ,and [ xy ] is the edge of t that faces [ pq ] ;
4. the edge-segment ( zp ] of e 1 (resp., ( zq ] of e 2 )doesnotintersecte 2 (resp.,
e 1 ); and
5.
|
f
|≥
5 or
|
f
|
=4 and
|
V ( f )
|≥
1 .
Step 2: Charging 0 -triangles. Let t be a 0-triangle, let e be one of its edges,
let f be the distant neighbor of t at e , and let e be the edge of f that faces t .
We move 1 / 3 units of charge from f to t , and say that f contributed 1 / 3 units
of charge to t through e .
In a similar way t obtains 1 / 3 units of charge from each of its distant neighbors
at its other edges.
After the second discharging step the charge of every 0-triangle becomes zero.
It remains to deal with 1-triangles, and then to make sure that the charge of
every face did not become negative after the discharging steps. Let t be a 1-
triangle and let A
V ( D )bethevertexof D that is incident to t .Let g be
an immediate neighbor of t that is incident to A .Wecall g a good neighbor of
Search WWH ::




Custom Search