Spatial search with polyhedra

Range searches in multidimensional space have been studied extensively, and several excellent search structures have been devised. However, all of these require that the ranges in the different dimensions be specified independently. In other words, only rectangular regions can be specified and searched for. Similarly, nonpoint objects can be indexed only in terms of their bounding rectangles. However, polyhedral search regions and polyhedral bounding rectangles can often provide a much greater selectivity in the search. It is shown how to use multiattribute search structures for polyhedral regions by mapping polyhedral regions into rectangular regions of a higher dimension. In particular, the P-tree (polyhedral tree) is introduced and shown to be an effective multiattribute index structure