用三个最短的正方形覆盖n个点

Question

用三个最短的正方形覆盖n个点

algorithmpoint

4

给定一组 n 个点 (a_1, b_1), (a_2, b_2), ..., (a_n, b_n)。需要找到最小的 x ，使得三个 轴平行 的边长为 x 的正方形覆盖所有点。

我可以找到包含所有点的最小面积矩形。这个矩形能否被用来解决这个问题？还是说有什么提示可以解决这个问题？

- Artur

也许可以使用某种聚类算法将点分成三组，然后分别用一个正方形覆盖它们？ - tobias_k

2个回答

2

@EvgenyKluev的回答似乎朝着正确的方向，但还有一些细微之处需要注意。

由于我没有看到对整数x的限制，因此您可能希望在x上进行二分搜索以指导您的算法，并在仍然可用于x的范围足够小的情况下找到合适的终止条件（您也可以在整数x上进行二分搜索，但是在那里您不需要终止条件）。

将正方形放置在矩形的一个角落（您将不得不这样做，这是相当容易证明的）会限制您放置其他两个正方形的搜索空间：让A成为由与角对齐的第一个正方形覆盖的点组成的集合，S是所有点的集合。取S-A并找到该点集的外接矩形。将剩余的两个正方形放置在S-A的外接矩形的相对角落上始终是一种解决方案（只有一对相对角落可能适合），如果存在的话。

因此，一种算法可以-非常高级-像这样进行。

binary search for x on [0,N]:
    find R(S), the enclosing rectangle of S
    for each corner C of R(S):
        align one square at C, let the points covered by that square be A
        find R(S-A)
        do two squares aligned at opposite corners of R(S-A) cover S-A?

关于二分查找，我无法确切地说它会以多快的速度收敛到只允许一个正方形对齐的范围，在这一点上，您可以直接计算值x。我认为使用任意精度，您可以使其变得非常糟糕。每次迭代需要O(nlogn)来排序两个基本方向上的点。

- G. Bach

这种方法也相当不错。关于二分查找的几点评论：如果我们对所有x和y坐标（减去“起始”角落的坐标）进行排序，并使用结果数组进行二分查找，则只需要O(log n)个搜索步骤。由于所有其他操作最多可以用两次线性扫描完成，因此整个算法的最坏情况复杂度为O(n log n)。 - Evgeny Kluev

@EvgenyKluev 听起来很对。在你澄清如何将其用于二分查找之前，我没有正确理解你的想法，这就是为什么我认为它需要澄清的原因。很高兴现在我明白了！ - G. Bach

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Evgeny Kluev · Accepted Answer

我认为，只需要考虑两种情况：

每个正方形都接触到最小矩形的一条边。
当两个正方形位于最小矩形的对角线处，第三个正方形在内部（不接触最小矩形的任何一条边）。

在第一种情况下，我们可以将一个正方形的角固定在矩形的其中一个角上，然后将另外两个正方形的角固定在该角的两条相对边上（每个正方形有n种可能的位置），然后对于每个点，确定其所属的最佳正方形和最小的x值。

在第二种情况下，尝试最小矩形的两个相对角落作为“外部”正方形的位置，然后将“内部”正方形的一个角固定在所有由所有x和y坐标确定的n*n个位置中的一个上，然后对于每个点，确定其所属的最佳正方形和最小的x值。

时间复杂度为O（n³）。