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
∈