Range minima queries with respect to a random permutation, and approximate range counting (Q629829)

Let \(P\) be a finite set of points in \(\mathbb{R}^d\). The approximate range counting problem, addressed in the paper under review, is the task to preprocess \(P\) into a data structure, which, for a given relative tolerance \(\epsilon\), answers efficiently queries of the following form: Given a halfspace \(H\subset\mathbb{R}^d\), compute an \(N\) such that \((1-\epsilon)|P\cap H|\leq N\leq (1+\epsilon)|P\cap H|\). Using \textit{E. Cohen}'s ``small number of random permutations'' strategy for approximate range counting [J. Comput. Syst. Sci. 55, No. 3, 441--453 (1997; Zbl 0897.68075)], the authors present a new approach to this problem, which for each permutation needs \(O(n^{\lfloor d/2\rfloor}(\log\log n)^{\mathrm{const}}/\log^{\lfloor d/2\rfloor }n)\) expected storage and preprocessing time, and answers queries in \(O(\log n)\) expected time.