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

Question

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

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

Answer 1

我觉得，分两种情况就够了:

1. 当每个正方形都接触到面积最小的矩形的某条边时。
2. 当两个正方形位于最小面积矩形的对角而第三个位于内部(不接触最小面积矩形的任何边缘)时。

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

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

时间复杂度为 O(n³)。