Information Technology Reference
In-Depth Information
B ( W )= H ∈W H
J ( W )= {
B i
For
W ⊆ B,
put
,
i :
(
j
) ∈ W
for some j
}
and J ( W )= {
B i
B i
)= B i
i :
(
j
) ∈ W
for some j
}.
Now
(
j
(
1
)
so
.
B i
B i
|B ( W ) | =
(
1
)
(
1
)
i
J ( W )
i
J ( W )
Note that J ( W )
J ( W )=
0 implies
|W |≤|B|/
2
.
We will divide the analy-
sis into several cases and for each case we will show that
|B ( W ) |≥|W |
; the cases
are expressed in terms of J ( W )
but the corresponding cases for J ( W )
follow
by symmetry and we will often use this fact without explicitly mentioning it in the
arguments below.
Case 1. Suppose J ( W )
contains i 1 and i 2 satisfying
|
i 1
i 2 | >
1
.
Because b
a
,
at least one of A i
) ∈ B i 1 (
and A i
) ∈ B i 2 (
for each i and j
,
(
j
1
)
(
j
1
)
holds and at
least one of A i
) ∈B i 1 (
and A i
) ∈ B i 2 (
(
j
1
)
(
j
1
)
holds. Hence we have
B ( W )=
Y ∪Y = Y
|B ( W ) | = |B|≥|W |.
Thus we can assume that
and
J ( W ) |≤
J ( W ) | =
|
2
.
Furthermore, if
|
2
,
then
J ( W )= {
|Y |− (
k
.
k
+
1
}
for some integer k so that
B ( W )
contains at least
s
Y .
This follows because A i
A i
λ s + λ q
q
)
members of
(
j
) ∈B ( W )
if kb
(
j
) .
|Y |− (
Y .
Similarly
B ( W )
contains at least
s
λ s )
members of
Case 2. Suppose J ( W )
B i
( W ) ⊇ Y and
contains an i
q
.
We t h e n h ave
holds when J ( W )
J ( W )=
|B ( W ) |≥|B|/
2
.
Hence
|B ( W ) |≥|W |
/0or
J ( W )
.
contains a k
q
Thus, by Case 1 , we only have to consider the case
J ( W )= {
J ( W )
and J ( W ) ∩{
,
+
},
+
,
,...,
} =
.
q
q
1
q
1
1
2
q
0
, B q + 1 (
Y so
=
)
λ
+ λ
|B ( W ) |≥
If
λ
0
j
contains at least s
q members of
s
s
q
J ( W )
J ( W ) | =
|B|/
2
+
s
λ s + λ q
q
≥|W |
because
|
1
.
Now A i
int A i
If
λ s =
0
,
s
3 because 2 b
<
1
.
(
j
) ∈ B ( W )
if qb
(
j
) .
There
Y having qb as an interior point so
are at most s
λ s members of
B ( W )
contains
Y .
at least
(
s
λ q
q
λ s ) (
s
λ s )=
s
λ q
s members of
Now s
q
+ λ q because
(
q
+ λ q )
b
qb
+ λ q a
1
> (
s
1
)
b
.
Thus
|B ( W ) |≥|B|/
2
+
s
λ q
s
≥|B|/
2
+
because J ( W )
J ( W )= {
(
s
1
) λ q
q
≥|B|/
2
+ λ q
q
≥|W |
q
+
1
}.
By Cases 1 and 2 we can now assume
J ( W ) |≤
J ( W ) |≤
|
2
,
and
|
2
(9.7)
and
J ( W )
J ( W )
i
implies i
>
q
.
(9.8)
Thus
J ( W ) | + |
J ( W ) | ) .
|W |≤ ( λ q
q
)( |
(9.9)
Case 3. Suppose J ( W )= {
k
,
k
+
1
}
where k
>
q
.
We have already shown that,
Y and at least
for this case,
B ( W )
contains at least s
λ q
q
λ s (
s
λ s )
of the
Y .
J ( W ) | =
s
λ q
q
λ s (
s
λ s + λ q
q
)
of the
Furthermore, if
|
2
, B ( W )
Y .
contains at least s
λ q
q
λ s (
s
λ s )
members of
Thus
Search WWH ::




Custom Search