Epsilon-nets and simplex range queries

We present a new technique for half-space and simplex range query using Ο(n) space and Ο(na) query time, where a < d(d-1)/d(d-1) + 1 + γ for all dimensions d ≥ 2 and γ > 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.