找到k个矩形，以便它们覆盖最大点数 [英] Find k rectangles so that they cover the maximum number of points

问题描述

在二维空间中，给定了一堆矩形，每个矩形覆盖多个点，并且在两个任意矩形之间可能存在重叠，对于指定数量K，如何找到k个矩形，使得它们的联合覆盖最高点数？
在这个问题中，如果一个点被两个以上的矩形所覆盖，那么它只计算一次，我们假设位置&矩形的大小和点的位置是固定的，如输入中所给出的。

有人可以给我用于解决它的算法吗？或者指出它可以减少到一些已知的问题？

解决方案

这看起来像几何版本的最大覆盖率问题与设置封面问题，这两个是NP-Complete。

从我能找到的，它看起来像几何版本的Set Cover也是NP-Complete，这里的论文有一个快速近似算法，它利用它是几何的： http://www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf 。 Set Cover的几何版本是NP-Complete的事实意味着最大覆盖率问题的几何版本也是NP-Complete。

当然，你的特殊情况的矩形集合可能仍然适用于精确的多项式时间算法，但我怀疑。也许上述文章中的参考文献可能会导致您获得一个很好的解决方案。

希望有帮助！

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?

解决方案

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!

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