Lower bounds on the complexity of multidimensional searching
Bernard Chazelle · 1986
We establish new lower bounds on the complexity of several searching problems. We show that the time for solving the partial sum problem on n points in d dimensions is at least proportional to (log n/log 2m/n)d-1 in both the worst and average cases; m denotes the amount of storage used. This bound is provably tight for m = Ω(nlogcn) and any c ≫ d- 1. We also prove a lower bound of Ω(n(log n/log log n)d) on the time required for executing n inserts and queries. Other results include a lower bound on the complexity of orthogonal range searching in d dimensions (in report-mode). We show that on a pointer machine a query time of O(s+polylog(n)) time can only be achieved at the expense of Ω(n(log n/log log n)d-1) space, which is optimal; n and s denote respectively the input and output sizes.