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.
 
Search WWH ::




Custom Search