Lower Bounds on the Complexity of Multidimensional Searching

Abstract:

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.