从一组点中找到最大矩形的有效算法

Question

我有一系列点，我的目标是选择两个点，以便最大化这两个点（一个代表左下角，另一个代表右上角）形成的矩形面积。

我可以通过执行两个 for 循环并计算每个可能的区域来在 O(n^2) 中完成此操作，但我认为必须有一个更有效的解决方案：

max_area = 0
for p1 in points:
    for p2 in points:
       area = p2[0]p2[1] + p1[0]p1[1] - p2[1]p1[0] - p2[0]p1[1]
       if area > max_area:
           max_area = area

很明显，我想以原点 (0,0) 最大化第二个点的面积（因此 p2[0]p2[1]），但我不确定如何继续。

Answer 1

分而治之。

注意：该算法假定矩形是轴对齐的。

• 第 1 步：将点放入 4x4 桶的网格中。有些桶可能会变空。
• 步骤 2：使用桶的角，计算非空桶之间对角的最大面积。这可能会产生几对桶，因为您使用的是角，而不是点。
  另请注意，您对左桶使用左角，对 b、r、t 桶使用下角、右角、顶角。这就是为什么网格大小使用偶数的原因。
• 步骤 3：将步骤 2 中选择的每个存储桶重新存储为新的、更小的 4x4 网格。
• 重复步骤 2 和 3，直到获得一对仅包含每个桶中一个点的桶。

我没有计算过这个算法的复杂度。看起来 O(n log(n))。