algorithm - Find k rectangles so that they cover the maximum number of points

Question

In two dimensional space, given a bunch of rectangles, every rectangle covers a number of points and there may be overlap between two arbitrary rectangles, for a specified number K, how can i find the k rectangles such that their union cover the maximum number of points? In this problem, if a point is covered by more than two rectangles it is only counted once and we assume that the positions & size of rectangles and positions of points are fixed as given in the input.

Can someone give me the algorithm used to solve it? Or point out that it can be reduced to some known problem?

Answer 1

This looks like a geometric version of the Maximum Coverage Problem which is closely related to the Set Cover Problem, and those two are NP-Complete.

From what I could find, it looks like the Geometric version of Set Cover is also NP-Complete and the paper here has a fast approximation algorithm which exploits the fact that it is geometric: http://www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf. The fact the the geometric version of Set Cover is NP-Complete implies that the geometric version of the Maximum Coverage problem is also NP-Complete.

Of course, your special case of the sets being rectangles might still lend itself to exact polynomial time algorithms, but I doubt it. Perhaps the references in the above paper might lead you to a good solution.

Hope that helps!