Translating a Regular Grid over a Point Set

Abstract

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 5. The main set of problems we study have to do with translating an infinite grid so that the number of fe-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 fe-occupied cells. Here we obtain a running time of the form O(knm polylog nm).