给定一组 n
个点 (a_1, b_1)
, (a_2, b_2)
, ..., (a_n, b_n)
。需要找到最小的 x
,使得三个 轴平行
的边长为 x
的正方形覆盖所有点。
我可以找到包含所有点的最小面积矩形。这个矩形能否被用来解决这个问题?还是说有什么提示可以解决这个问题?
我认为,只需要考虑两种情况:
在第一种情况下,我们可以将一个正方形的角固定在矩形的其中一个角上,然后将另外两个正方形的角固定在该角的两条相对边上(每个正方形有n种可能的位置),然后对于每个点,确定其所属的最佳正方形和最小的x值。
在第二种情况下,尝试最小矩形的两个相对角落作为“外部”正方形的位置,然后将“内部”正方形的一个角固定在所有由所有x和y坐标确定的n*n个位置中的一个上,然后对于每个点,确定其所属的最佳正方形和最小的x值。
时间复杂度为O(n³)。
n
是点的数量,k
是正方形的数量,在 O(k * n^3)
的时间复杂度下完成是我目前能想出的最好的方法。 - G. Bachk>3
。对我来说,一个不同的泛化更有趣:如果k
保持较小(2或3),但点是按顺序逐个添加的;在每个新点之后找到x
的最佳时间复杂度是多少? - Evgeny Kluevbinary 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)来排序两个基本方向上的点。