找到 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-Complete.

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.

据我所知，Set Cover 的 Geometric 版本似乎也是 NP-Complete 并且这里的论文有一个快速逼近算法，它利用了它是几何的这一事实:http://www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf.Set Cover 的几何版本是 NP-Complete 的事实意味着最大覆盖问题的几何版本也是 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.

希望有帮助！

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