Figure 1: A quadtree: the data partition the unitcube recursively into quadrants; the quadtree corresponds to this partitioning.
C_{n} = 1_{Y < U} 
æ ç ç è 
C 

+ C 

ö ÷ ÷ ø 
+ 1_{Y > U} 
æ ç ç è 
C 

+ C 

ö ÷ ÷ ø 
+ 1, 
E  [C_{n}] ~ g n 

, Var  [C_{n}] ~ b n 

. 
I^{n}/n ® W =  (  UV,U(1V),(1U)V,(1U)(1V)  ) 

(2) 



X_{n} = 

. 
Y_{n} = 

Y 

+ n. 
X_{n} = 


X 

+ C_{n}(I^{n}) 
C_{n}(i_{0},...,i 

) = 1 + 


E  [Y 

]  E[Y_{n}]. 
C_{n}(i) = 1 + 



ln 

+ o(1). 
C_{n} = 1 

C' 

+ 1 

C'' 

+ n  1 
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.