Translating a regular grid over a point set (Q1873153)

The authors consider the problem of translating a finite or infinity square grid \(G\) over a set \(S\) of \(n\) points in the plane in order to maximize some objective function. A grid cell in \(k\)-occupied if it contains \(K\) or more points of \(S\). The main set of problems studied have to do with translating an infinity grid so that the number of \(k\)-occupied cells is maximized or minimized. For these problems running times of the form \(O(kn\text{ poly log}(n))\) are obtained. Also the problem of translating a finite size grid, with \(m\) cells, is considered in order to maximize the number of \(k\)-occupied cells.