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

I think You need combinatorial optimization algorithm which can select values/nodes(eg here rectangles) so that given function gives maxima. I don't know it in detail but you can try optimization in MATLAB

Answer 2

I'm assuming you have fixed rectangles (i.e., you can't choose how big your rectangles are, and where they are positioned). If you could choose the size of the rectangles, the problem would be trivial. If you could choose where to position your rectangles, this would also be a different problem (solved by another greedy algorithm).

For more details, you need to tell us how your rectangles and points are specified, and how they are stocked---or whether you need help picking a good data structure given your input format.

Now, a greedy solution to your problem is to proceed as follow. Initially begin with all rectangles "chosen" as covering points. Then, one by one, remove the rectangle covering the least amount of points, until you have only K rectangles in your set. The complexity of this algorithm is polynomial, and its efficiency hinges on how you are going to implement the query "find out which rectangle covers the least points". Using a heap, you could do this in O(1), with a pre-processing phase to build the heap (the complexity of which will depend on how your points are stored).

EDIT : the problem with this solution is that at each step, the answer to "will make it so I have the least amount of points uncovered" is not unique, several rectangles can, at that step, fill the criterion; in the end, it may turn out that one choice would have been better than another, and this could not have been determined at that step...

   /---------\
   |2        |
/-----\   /-------\
|1 | *|   |* |   3|
\-----/   \-------/
   |         |
   \---------/

For example, here, all rectangles are tied: if you remove any one rectangle, you will uncover no points. However it is obvious to see that the best 1-solution is to have rectangle 2 cover the points (note that rectangles 1 and 3 could be arbitrarily wide, so size is not a telling factor).

Answer 3

If you have n rectangles, k of which you have to choose, then there are (choose n k) different combinations, i.e. (/ (factorial n) (factorial k) (factorial (- n k))). In the general case, I suspect that you have to enumerate these combinations and calculate their coverage. However, you might be able to cut this short a bit by ordering the rectangles by coverage (i.e. number of points covered by themselves), starting with the combination of the biggest rectangles, and stopping when the remaining rectangles cannot surpass your previously best combination.

Answer 4

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!