找到覆盖2D点数组的最小矩形数

Question

我得到了一个二维点数组，任务是生成一个最小的矩形列表，其中所有矩形具有相同的大小和方向，它们覆盖所有的二维点位置并且可以重叠。

到目前为止，我有一个不太令人满意的解决方案，其中选择数组中的第一个点作为第一个矩形的中心，然后移动该矩形，以使最接近的点适合其中。重复该过程，直到已经覆盖如果要再次移动矩形，则将丢失点。之后，从下一个未发现的点开始重复该过程，直到没有剩余的点为止。不太令人满意。

目标是找出最佳算法。它不必是矩形的绝对最小数目，而应尽可能少。

Answer 1

首先，可以以如下方式平移/投影坐标，即矩形大小为1x1，方向为0°（与X / Y轴对齐）。所以我会假设这种情况。

然后您可以按照以下步骤进行：

1. 按其x-坐标对点进行排序
2. 创建如下的有向图：
   • 对于每个点a，取x区间[aa [[x，a _x + 1]中的点，但不包括_{a] >本身从该列表中排除其}
   • y
   坐标不在[a y-1，a _y + 1]]中的那些点通过
   • y-坐标对这些点进行排序
   将这些点放在邻接点列表中，作为点
   • a
   。
将所有点标记为未访问
3. 如果没有未访问的点，则返回0表示不需要（更多）矩形。
4. 从已排序的点列表中获取下一个未访问的点
5. a
：将a标记为已访问。如果
6. a
没有邻居，则增加矩形数并从步骤4开始重复在矩形上滑动其左
7. x
-坐标始终等于a x的矩形，使得：
第一个选择的矩形具有与第一个未访问的相邻点相同的低-[[y
-坐标]
8. 通过被这个矩形覆盖，维护被访问邻居的列表L（仅当尚未将其标记为已访问）时>]
9. 所有下一个矩形位置均在其高y
坐标端获得一个未访问的点。
10. L
中在滑动矩形的下-
11. y侧未被发现的点被从L
移除并再次标记为未访问]每次确定新的矩形位置时，都会从第4步开始进行递归（DFS）调用。DFS调用将返回仍然需要覆盖所有其余未访问点的矩形数
12. 保留所有这些递归调用返回的最小值，并加1（对于当前矩形）
13. 注意：可以通过将当前的最小结果作为截止点来修剪递归树，以免搜索会增加太多矩形数。
14. 处理完所有矩形位置后，将仍在[[L
中的任何点标记为未访问。
15. 返回找到的最小矩形数。
16. 这可能仍然是一个非常昂贵的算法，因为搜索树很容易变得非常宽。
一个潜在的改进可能是使用BFS而不是DFS，并使用优先级队列（例如Min Heap）。最小化的数字将是已经使用的矩形的数量（即，到目前为止的成本）加上最右边（未访问）的点与最左边未访问点之间的x坐标差，向上舍入（即，成本的下限）仍然领先）。这是一个A *算法。
17. 此BFS方法的缺点是内存使用和管理，因为每个状态（在优先级队列中）都包含一组访问点。