IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS

We investigate one of the fundamental areas in computational geometry: lower bounds for range reporting problems in the pointer machine and the external memory models. We develop new techniques that lead to new and improved lower bounds for simplex range reporting as well as some other geometric problems. Simplex range reporting is the problem of storing n points in the d-dimensional space in a data structure such that the k points that lie inside a query simplex can be found efficiently. This is one of the fundamental and extensively studied problems in computational geometry. Currently, the best data structures for the problem achieve Q(n) + O(k) query time using (O) over tilde((n/ Q(n))(d)) space in which the (O) over tilde(.) notation either hides a polylogarithmic or an n(epsilon) factor for any constant epsilon > 0, (depending on the data structure and Q (n)). The best lower bound on this problem is due to Chazelle and Rosenberg who showed any pointer machine data structure that can answer queries in O(n(gamma) + k) time must use Omega(n(d-epsilon-d gamma)) space. Observe that this bound is a polynomial factor away from the best known data structures. In this article, we improve the space lower bound to Omega ((n/Q(n))(d)/2(O(root log Q(n)))). Not only this bridges the gap from polynomial to sub-polynomial, it also offers a smooth trade-off curve. For instance, for polylogarithmic values of Q(n), our space lower bound almost equals Omega((n/Q(n))(d)); the latter is generally believed to be the "right" bound. By a simple geometric transformation, we also improve the best lower bounds for the halfspace range reporting problem. Furthermore, we study the external memory model and offer a new simple framework for proving lower bounds in this model. We show that answering simplex range reporting queries with Q(n) + O(k/B) I/Os requires Omega(B(n/(BQ(n)))(d)/2(O(root logQ (n)))) space or Omega((n/(BQ(n)))(d)/2(O(root logQ(n)))) blocks, in which B is the block size.