General methods for adding range restrictions to decomposable searching problems (Q1118417)

The problem of adding range restrictions to decomposable searching problems consists in associating a new parameter with every element of the given set of objects. Thus, queries will be restricted to those objects that have this new parameter in a certain given range. Two classes of structures for this problem are presented. The first class contains structures that have low storage cost at an expense of increased query time. The structure of the second class have much better query time but need more storage and preprocessing time. Both classes can be tuned to obtain different structures with different trade-offs for query time, memory cost and preprocessing time. In addition, the authors introduce a new weight-balanced multiway tree and use it to transform the previous static structures into dynamic structures with reasonable insertion and deletion times. Finally, they apply the results to the d-dimensional range searching problem and obtain a whole class of structures containing most of the known results and adding new ones.