Key points are not available for this paper at this time.
We present a new technique for half-space and simplex range query using Ο(n) space and Ο(na) query time, where a 0. These bounds are better than those previously published for all d ≥ 2. The technique uses random sampling to build a partition-tree structure. We introduce the concept of an ε-net for an abstract set of ranges to describe the desired result of this random sampling and give necessary and sufficient conditions that a random sample is an ε-net with high probability. We illustrate the application of these ideas to other range query problems.
Haussler et al. (Wed,) studied this question.