2003-05-01

# Translating a regular grid over a point set

## Publication

### Publication

*Computational Geometry , Volume 25 - Issue 1-2 p. 21- 34*

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(logn) time per operation, a function f:R→R under the following query and update operations where [a,b) is a continuous interval in R: Insert(T,a,b,δ): Increase the value of f(x) by δ for all x∈[a,b). Delete(T,a,b,δ): Decrease the value of f(x) by δ for all x∈[a,b). Max-Cover(): Return max{f(x): x∈R}. Max-Cover-Witness(): Return a value x(*) such that f(x(*))=max{f(x): x∈R}. Max-In(a,b): Returns max{f(x): x∈[a,b)}. Max-Witness-In(a,b): Returns a value x(*) such that f(x(*))=max{f(x): x∈[a,b)}. as well as the min counter-parts of these queries.

Additional Metadata | |
---|---|

Keywords | Binary tree, Dynamic data structure, Facility location, Intervals, Lazy update, Maintenance of functions |

Persistent URL | dx.doi.org/10.1016/S0925-7721(02)00128-1 |

Journal | Computational Geometry |

Citation |
Bose, P, Van Kreveld, M. (Marc), Maheshwari, A, Morin, P, & Morrison, J. (Jason). (2003). Translating a regular grid over a point set.
Computational Geometry, 25(1-2), 21–34. doi:10.1016/S0925-7721(02)00128-1 |