Improved Range Searching Lower Bounds

摘要

In this paper we present a number of improved lower bounds for range searching in the pointer machine and the group model. In the pointer machine, we prove lower bounds for the approximate simplex range reporting problem. In approximate simplex range reporting, points that lie within a distance of ε · diam(.s) from the border of a query simplex s, are free to be included or excluded from the output, where ε > 0 is an input parameter to the range searching problem. We prove our lower bounds by constructing a hard input set and query set, and then invoking Chazelle and Rosenberg's [CGTA'96] general theorem on the complexity of navigation in the pointer machine. For the group model, we show that input sets and query-sets that are hard for range reporting in the pointer machine (i.e. by Chazelle and Rosenberg's theorem), are also hard for dynamic range searching in the group model. This theorem allows us to reuse decades of research on range reporting lower bounds to immediately obtain a range of new group model lower bounds. Amongst others, this includes an improved lower bound for the fundamental problem of dynamic d-dimensional orthogonal range searching, stating that t_qt_u = Q((lgn/lg lg n)~(d-1)). Here t_q denotes the query time and t_u the update time of the data structure. This is an improvement of a lg~(1-δ) factor over the recent lower bound of Larsen [FOCS'11], where δ > 0 is a small constant depending on the dimension.