We establish new upper bounds on the complexity of multidimensional searching. Our results include, in particular, linear-size data structures for range and rectangle counting in two dimensions with logarithmic query time. More generally, we give improved data structures for rectangle problems in any dimension, in a static as well as dynamic setting. Several of the algorithms we give are simple to implement and might be the solutions of choice in practice. Central to this paper is the nonstandard approach followed to achieve these results. At its root we find a redefinition of data structures in terms of functional specifications.
|Original language||English (US)|
|Number of pages||36|
|Journal||SIAM Journal on Computing|
|State||Published - 1988|
All Science Journal Classification (ASJC) codes
- Computer Science(all)