Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems

Abstract:

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a set P of n points in Rd so that, given any query simplex q, the points in P intersect q can be counted or reported efficiently. If m units of storage are available (n 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.