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 a data structure such that the k points that lie inside a query simplex can be outputted 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((n/Q(n))~d) space in which the O(.) notation either hides a polylogarith-mic or an n~ε factor for any constant ε > 0, (depending on the data structure and Q(n)). The best lower bound on this problem is due to Chazelle and Rosenberg who proved a space lower bound of Ω(n~(d-ε-dr)) for pointer machine data structures that can answer queries in O(n~r + k) time. For data structures with Q(n) + O(k) query time, we improve the space lower bound to Ω((n/Q(n))~d/2~(O(√(1/2)(log Q(n))))). Not only this reduces the overhead from polynomial to sub-polynomial, it also offers a smooth trade-off curve. For instance, for polylogarithmic values of Q(n), our lower bound is within a o(log n) factor of the conjectured trade-off curve. By a simple geometric transformation, we also improve the best lower bounds for the halfspace range reporting problem. Furthermore, we also study the external memory model and offer a new framework for proving lower bound in this model. For the first time we show that answering simplex range reporting queries with Q(n) + k/B I/Os requires Ω(B(n/(BQ(n)))~d/2~(O(√(1/2)(log Q(n))) space in which B is the block size.