A family of data structures is presented for retrieval of the sum of values of points within a half-plane or polygon, given that the points are on integer coordinates in the plane. Fredman has shown that the problem has a lower bound of Ω(N^2/3) for intermixed updates and retrievals. Willard has shown an upper bound of O(N^2log6^4) for the case where the points are not restricted to integer coordinates.

We have developed families of related data structures for retrievals of half-planes or polygons. One of the data structures permits intermixed updates and half-plane retrievals in O(N^2/3log N) time, where N is the size of the grid.

We use a technique we call "Rotation" to permit a better match of a portion of the data structure to the particular problem. Rotations appear to be an effective method for trading-off storage redundancy against retrieval time for certain classes of problems.

We consider the problem of packing n items which are drawn according to a probability distribution whose density function is triangular in shape. For triangles which represent density functions whose expectation is 1/p for p = 3, 4, 5, ..., we give a packing strategy for which the ratio of the number of bins used in the packing to the expected total size of the items asymptotically approaches 1.