In the course of working with standard computational geometry algorithms in developing image conversion tools, we encountered several different problems of scale and representation. None of the algorithms in the literature had a unified solution that coupled the representation of spatial entities with the requisite access algorithms. Our data structure was specifically designed to handle objects that occupy a sub-area of an image, and the corresponding access methods allow for both two dimensional range queries and quick access to single objects. In the process of image conversion, fast range queries are essential when trying to quickly answer questions of nearness, connectedness, containment and intersection.
As the number of objects that needed to be managed grew, often to the tens or hundreds of thousands, the problems with standard representations grew intolerable.
Specifically, we saw the absolute need for data structures which had 
space requirements.
While there are several access algorithms that perform range searches using 
space, such as in [3], [4] and [5], the increase in storage requirements when going from 
to 
for this number of objects is quite intolerable, a 10 to 20 times increase in storage costs.
(For a discussion of space-time trade-offs for range searching problems, see [6].)
In addition, there was no clean way to implement efficient range searches on non-point objects.
Standard methods always led to an 
worst case performance.
The reason for this is that the objects were being represented geometrically as either a single two-dimensional point or a set of two-dimensional points, failing to capture the actual space which was occupied.
We will first present an interesting representation for rectangular objects. This representation allows us to simplify the requirements of the range query system while still utilizing a (four dimensional) point representation. Then, we will present a tree structure for manipulating these point objects and present the space and time requirements. Finally, we will show empirical results on both simulated and real-world data.