Database Reference
In-Depth Information
1
|
x
∈
N
G
h
(
x
,
o
)
×
|
N
|
1
|
x
∈
N
G
h
(
x
,
o
)
LT
(
o
,{
o
},
N
(
o
,
O
,
A
)
,
σ )
·
Pr
(
N
)=
|
=
|
N
|
O
|
O
Thus,
T
(
o
,
N
(
o
,
O
,
A
))
Pr
(
N
(
o
,
O
,
A
))
−
LT
(
o
,{
o
},
N
(
o
,
O
,
A
)
,
σ )
Pr
(
N
)
∑
x
∈
N
(
o
,
O
,
A
)
)
=
1
1
=
G
h
(
x
,
o
)
−
∑
x
∈
N
G
h
(
x
,
o
|
∑
x
∈
N
(
o
,
O
,
A
)
−
N
G
h
(
x
,
o
)
h
|
O
|
h
|
O
For instance
x
∈
N
(
o
,
O
,
A
)
−
N
,
x
is not in the
σ
-neighborhood of
o
,so
d
(
x
,
o
)
>
σ
.
Therefore
N
e
−
σ
2
1
h
|
O
|
∑
1
N
G
h
(
x
,
o
)
<
π
∑
√
2
2
h
2
x
∈
N
(
o
,
O
,
A
)
−
x
∈
N
(
o
,
O
,
A
)
−
h
|
O
|
Thus, we have
GT
(
A
,
O
)
−
LGT
(
A
,
O
,
σ )
=
∑
(
T
(
o
,
N
(
o
,
O
,
A
))
Pr
(
N
(
o
,
O
,
A
))
−
LT
(
o
,{
o
},
N
(
o
,
O
,
A
)
,
σ )
Pr
(
N
))
o
∈
A
e
−
σ
2
1
1
1
√
2
=
∑
o
∈
A
|
∑
x
∈
N
(
o
,
O
,
A
)
−
N
G
h
(
x
,
o
)
<
|
∑
o
∈
A
∑
x
∈
N
(
o
,
O
,
A
)
−
N
2
h
2
h
|
O
h
|
O
π
e
−
σ
2
1
h
√
2
<
2
h
2
π
Equation 4.15 holds.
Proof of Theorem 4.7.
For any instance
x
∈
O
,
RT
(
o
,
A
,
O
)=
GT
(
A
∪{
o
},
O
)
−
GT
(
A
,
O
)
,
σ)=
(
∪{
},
,
σ )
−
(
,
,
σ )
LRT
(
o
,
A
,
O
LGT
A
o
O
LGT
A
O
Therefore,
RT
(
o
,
A
,
O
)
−
LRT
(
o
,
A
,
O
,
σ )
=(
GT
(
A
∪{
o
},
O
)
−
LGT
(
A
∪{
o
},
O
,
σ ))
−
(
GT
(
A
,
O
)
−
LGT
(
A
,
O
,
σ ))
Using Lemma 4.1, we have
1
h
√
2
e
−
σ
2
0
≤
GT
(
A
∪{
o
},
O
)
−
LGT
(
A
∪{
o
},
O
,
σ )
<
2
h
2
π
and
1
h
√
2
e
−
σ
2
0
≤
GT
(
A
,
O
)
−
LGT
(
A
,
O
,
σ )
<
2
h
2
π
Thus,
1
h
√
2
e
−
σ
2
1
h
√
2
e
−
σ
2
−
2
h
2
<
RT
(
o
,
A
,
O
)
−
LRT
(
o
,
A
,
O
,
σ )
<
2
h
2
π
π
Inequality 4.14 follows from the above inequality immediately.