给定一组 N 维整数点，我如何找到最小的 N 维长方体集（二维情况下的矩形），使得整数点在整数点集中当且仅当它包含在一个或多个长方体/矩形。整数点是指具有整数坐标的点。
例如，给定点 (1,0), (2, 0) 和 (3,1), (4,1) 最小的矩形集是 (1,0-2,0),(3,1-4, 1)，见下图：
2…… 1 ...## 0 .##.. 01234
显然我可以进行蛮力搜索，但我正在寻找一种更有效的算法，即使它仍然具有很高的复杂性。
Chris
问问题
461 次
3 回答
2
一般情况是NP-hard： http:
//www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1988.21976
看起来它可以近似为 O(log N)。在线看“A compendium of NP optimization questions”，搜索“MINIMUM RECTANGLE COVER”
此外，您的特定用例可能仍然可以有效解决。
于 2009-12-13T19:11:24.850 回答
1
定位现有点的方法有很多：
将这些点放入哈希图中以便快速查找。对于一般情况下，如果您尝试收集积分，您不知道积分会留下多少洞，这可能是最好的方法。在最坏的情况下，每个点都会得到一个矩形。
如果您有一个或几个 Z 坐标，请在位图中收集点（1 位深度）。只需打开位图中的像素。
如果你真的需要收集矩形中的点，你必须先将它们放入一个有序集合中（按坐标）。多次迭代这个集合。每次，从集合中取出第一个点。然后寻找任何与您已有的点左/右相邻的点。如果有，将它们连接成一条（水平）线。当你获得更多分数时，增加这条线。
当没有剩余点时，对线条执行相同的操作以增长矩形。
于 2009-07-16T14:00:58.287 回答
1
我假设您愿意容忍重叠的矩形，因为如果点是
4 .###.
3 ..#..
2 .###.
1 ..#..
0 .###.
01234
那么您可以覆盖四个重叠的矩形，但需要五个不重叠的矩形。
这个算法怎么样：
对于每个点，找到包含该点的最大矩形。最大的矩形是不能再大但仍然只是覆盖点的矩形。如果有两个最大的矩形，就选一个。将最大的矩形存储在某种删除重复项的数据结构中。完成对所有点的迭代后，矩形集必须覆盖所有点。
我不知道这是否实际上是一组最小的矩形，但我怀疑它是。
请注意，在上面的示例中，您将获得三个矩形：一个垂直，两个水平。
于 2009-12-01T22:48:05.227 回答