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

Question

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

我可以找到包含所有点的最小面积的矩形。这个矩形可以以某种方式使用吗？或者任何关于如何处理这个问题的提示？

Answer 1

@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?

至于二分搜索法，我真的不能说它会多快收敛到只允许一个正方形排列的范围，在这一点上，你可以直接计算值< code>x -我希望以任意的精度，你可以任意地变坏。每次迭代需要O(n log n)来对两个基本方向上的点进行排序。

Answer 2

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

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

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

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

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