Lower Bounds on the Complexity of Multidimensional Searching
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 = omega(n logc n) and any c > d - 1. We also prove a lower bound of
omega (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 omega(n(log n/ log log n)d-1) space, which is optimal; n and s denote respectively the input and output sizes.