Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
presented by Micha Sharir
Let P be a simple 3-Polytope n facets. Order the vertices according to
their height3. There is one vertex with updegree 3 at the beginning of our list and
one with updegree 0 at the end of the list. All vertices in-between have either
updegree 1 (1-vertices) or updegree 2 (2-vertices). For a vertex v, denote
by h1(v) the number of 1-vertices and by h2(v) the number of
2-vertices above v (including v itself). Let E(v) be the expected
number of steps for RANDOM EDGE to reach the sink starting from vand F(a,b) be the maximal expected number of steps for RANDOM EDGE
starting from a vertex v with h1(v)=a and h2(v)=b. We will sketch a
proof for
Let u be a vertex with h1(u)=a and h2(u)=b.
If u is a 1-vertex the expected cost E(u) is the expected cost of its only
successor v plus 1 (see fig. 4). Since
we get
For u being a 2-vertex there are several cases. Let v1,v2 be the two higher neighbors of u, v1 lower than v2. Then and .
If between u and v2 is a second vertex,
h1(v2)+h2(v2) looses two
additional vertices (see fig. 5). Therefore
and
For the rest of the proof we have to deal with the cases that v1 is
directly above u and v2 directly above v1. If v1 is a 1-vertex
(see fig. 6)
we get
and
.
This gives
Let now v1 be a 2-vertex. If we have no edge between v1 and v2 (see
fig. 7) we
get
and therefore
If there is an edge from v1 to v2 denote by w1 the second successor of v1 and by w2 the successor of v2. If w1=w2, the edge graph of P would be only 2-connected, a contradiction (see fig. 8).
Therefore we have
(see fig. 9). With probability
we will go
,
with probability
we have
and in all other cases we get
.
Therefore