Information Technology Reference
In-Depth Information
Assigning every face
f
∈
F
achargeof
|
f
|
|
V
(
f
)
|−
+
4, we get that total charge
over all faces is
E
|
E
|−
V
|−
F
|
(
|
f
|
+
|
V
(
f
)
|−
4) = 2
|
+2
|
4(
|
n
)
−
4
|
=4
n
−
8
,
f∈F
where the last equality follows from Euler's Polyhedral Formula by which
|
V
|
+
F
|−|
E
|
|
= 2 (recall that
M
(
D
) is connected).
Discharging.
We will redistribute the charges in several steps. We denote by
ch
i
(
x
) the charge of an element
x
(either a face in
F
or a vertex in
V
(
D
)) after
the
i
th step, where
ch
0
(
) represents the initial charge function. We will use the
terms
triangles
,
quadrilaterals
and
pentagons
to refer to faces of size 3, 4 and 5,
respectively. An integer before the name of a face denotes the number of original
vertices it is incident to. For example, a 2-triangle is a face of size 3 that is
incident to 2 original vertices.
Step 1: Charging the Vertices of
D
.
In this step every vertex of
D
takes
1
/
3 units of charge from each face it is incident to.
·
V
(
D
)is
3
deg(
A
). Next, we need
to make sure that the charge of every face is nonnegative. Let
f
After Step 1 the charge of every vertex
A
∈
F
be a face.
∈
+
3
|
Note that
ch
1
(
f
)
4. Recall
that
M
(
D
) has no faces of size two. Thus, it remains to consider the case that
f
is a triangle: if
f
is a 3-triangle, then
ch
1
(
f
)=1;if
f
is a 2-triangle, then
ch
1
(
f
)=
3
;if
f
is a 1-triangle, then
ch
1
(
f
)=
≥|
f
|
V
(
f
)
|−
4 and therefore
ch
1
(
f
)
≥
0if
|
f
|≥
1
−
3
;andif
f
is a 0-triangle, then
ch
1
(
f
)=
1.
In order to describe the way the charge of 0- and 1-triangles becomes nonneg-
ative, we will need the following definitions. Let
f
be a face, let
e
be one of its
edges, and let
f
be the other face that shares
e
with
f
.Wesaythat
f
is the
immediate neighbor
of
f
at
e
.
Let
f
0
be a face in
M
(
D
) and let
x
1
and
y
1
be two vertices of
f
0
that are
consecutive on its boundary and are crossing points in
D
.Denoteby
e
1
(resp.,
e
2
)the
D
-edge that crosses the
D
-edge that contains the edge-segment [
x
1
y
1
]
at
x
(resp.,
y
). Notice that it follows from Lemma 2 that
e
1
and
e
2
are distinct
D
-edges. Let
f
1
be the immediate neighbor of
f
0
at [
x
1
y
1
]. For
i
−
1, if
f
i
is a
0-quadrilateral, then denote by [
x
i
+1
y
i
+1
] the edge opposite to [
x
i
y
i
]in
f
i
,such
that
e
1
contains
x
i
+1
and
e
2
contains
y
i
+1
, and let
f
i
+1
be immediate neighbor
of
f
i
at [
x
i
+1
y
i
+1
] (see Fig. 2 for an illustration).
Clearly, it is impossible that
x
j
=
x
k
or
y
j
=
y
k
for
j
≥
=
k
,since
e
1
and
e
2
do
not cross themselves. Suppose that
x
j
=
y
k
for some
j
and
k
. Assume without
loss of generality that
j
k
. It cannot happen that
j
=
k
for then
f
j−
1
is not
a 0-quadrilateral. Since
x
j
=
y
k
,
e
2
crosses
e
1
at
x
j
.The
M
-edges [
x
j−
1
x
j
]and
[
x
j
x
j
+1
]arecontainedin
e
1
(note that [
x
j
x
j
+1
]existssince
j<k
). Therefore,
e
2
contains [
x
j
y
j
]. However, this implies that
e
2
crosses itself at
y
j
(see Fig. 2
for an illustration).
It follows that it cannot happen that there are two 0-quadrilaterals
f
i
and
f
j
such that
i
≤
=
j
and
f
i
=
f
j
. By Lemma 3 every edge in
D
contains at most
