Theorem 4.6 ([1]}, [2]}, [3]}) 
Let \((P,w,Q,f)\)  be a query space of dimension \(d\)  such that \(\sum _{p\in P}w(p)=1\)  and \(f:P\rightarrow [0,1]\) , and let \(\varepsilon ,\delta ,\nu >0\) . Let \(S\)  be a random sample from \(P\) , where every point \(p\in P\)  is sampled independently with probability \(w(p)\) . Assign a weight \(u(p)=\frac{1}{|S|}\)  for every \(p\in S\) .
If
\(|S|\in \Omega (1)\cdot \frac{1}{\varepsilon ^2\nu }\left(d\log \left(\frac{1}{\nu }\right)+\log \left(\frac{1}{\delta }\right)\right)\) 
