\(\epsilon\)-nets and simplex range queries (Q1089803)

The main problem may be described as follows: given a set of n points in d-dimensional Euclidean space, find a data structure that uses linear storage such that the number of points in any query half space can be determined in sublinear time \(O(n^{\alpha})\). A data structure with \(\alpha =d(d-1)/(d(d-1)+1)+\gamma\) for any \(\gamma >0\) is exhibited. These bounds for \(\alpha\) are better than those previously published for all \(d\geq 2\) by \textit{A. Yao} and \textit{F. Yao} [A general approach to d- dimensional geometric queries. Proc. 17th Symp. Theory of Computing, 163- 169 (1985)]. Let X be a set and R be a set of subsets of X, which have a finite dimension in Vapnik-Chervonenkis sense [\textit{V. N. Vapnik} and \textit{A. Ya. Chervonenkis}: The theory of pattern recognition (Russian) (1974; Zbl 0284.68070)], A be a finite subset of X and \(0\leq \epsilon \leq 1\). A subset N of A is an \(\epsilon\)-net of A (for R) if N contains a point in each \(r\in R\) such that \(| A\cap r| /| A| >\epsilon\). The authors prove that for \(0<\epsilon\), \(\delta <1\), if N is a subset of A obtained by \(m\geq \max (4/\epsilon \log 2/\delta,8d/\epsilon \log 8d/\epsilon)\) random independent draws, then N is an \(\epsilon\)-net of A with probability at least 1-\(\delta\). Using this result, a partition tree structure that achieves the above query time is constructed.