用三个最小长度的正方形覆盖n个点

Question

给定一组n点(a_1, b_1)，(a_2, b_2)。。。，(a_n, b_n)。需要找到最小x，使得每个长度为x的三个axis parallel平方一起覆盖所有点。

我可以找到包围所有点的面积最小的矩形。这个矩形可以用吗？或者有什么关于如何处理这个问题的提示吗？

Answer 1

我认为，考虑两种情况就足够了：

1. 当每个正方形接触到最小面积矩形的某个边缘时
2. 当两个正方形位于最小面积矩形的对角，而第三个正方形位于内侧（不接触最小面积矩形任何边缘）时

在第一种情况下，我们可以将一个正方形的角固定在4个矩形的角中的一个，然后将其他两个正方形的边固定在矩形的两个相对（与所选角）边的某个位置（每个边的n个可能位置），然后为每个点确定其所属的最佳正方形和最小x。

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

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

Answer 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（n-logn）来对两个基本方向上的点进行排序。