Translating a regular grid over a point set

We consider the problem of translating a (finite or infinite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if it contains k or more points of S. The main set of problems we study have to do with translating an infinite grid so that the number of k-occupied cells is maximized or minimized. For these problems we obtain running times of the form O(kn polylog (n)). We also consider the problem of translating a finite size grid, with m cells, in order to maximize the number of k-occupied cells. Here we obtain a running time of the form O(knm polylog (nm)). In solving these problems, we design a data structure T that maintains in O(log n) time per operation, a function f : R --> R under the following query and update operations where [a, b) is a continuous interval in R: 1. INSERT(T, a, b, delta): Increase the value of f (x) by delta for all x is an element of [a, b). 2. DELETE(T, a, b, delta): Decrease the value of f (x) by delta for all x is an element of [a, b). 3. MAX-COVER(): Return max{f (x): x is an element of R}. 4. MAX-COVER-WITNESS(): Return a value x* such that f (x*) = max{f (x): x is an element of R}. 5. MAX-IN(a, b): Returns max{f (x): x is an element of [a, b)}. 6. MAX-WITNESS-IN(a, b): Returns a value x* such that f (x*) = max{f (x): x is an element of [a, b)}. as well as the min counter-parts of these queries. (C) 2002 Published by Elsevier Science B.V.