Quasi-optimal upper bounds for simplex range searching and new zone theorems

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a set P of n points in ℜ^d so that, given any query simplex q, the points in P ∩q can be counted or reported efficiently. If m units of storage are available (n <m <n^d), then we show that it is possible to answer any query in O(n^1+e{open}/m^1/d) query time after O(m^1+e{open}) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieve O(log n) query time at the expense of O(n^d+e{open}) storage for any fixed e{open} > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.