得到k的矩形，使其覆盖点的最大数 [英] Find k rectangles so that they cover the maximum number of points

问题描述

在二维空间，给了一堆矩形，每个矩形覆盖多个点，并有可能是两个任意矩形之间的重叠，在指定的数K，我怎么能找到k个矩形，使得他们的结合覆盖最大点数？ 在这个问题，如果一个点覆盖多于两个矩形它只计数一次，我们假设位置＆安培;矩形和点的位置的大小被固定为在输入给出。

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?

推荐答案

这看起来像最大覆盖问题的这是密切相关的集合覆盖问题和这两个是NP完全问题。

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.

这是我能找到的，它看起来像集合覆盖的几何版本也是NP完全这里的纸具有快速近似算法它利用的事实，这是几何：的 http://www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf 。事实上集合覆盖的几何版本是NP完全意味着最大覆盖范围问题的几何版本也是NP完全问题。

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.

希望帮助！

这篇关于得到k的矩形，使其覆盖点的最大数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！