algorithm - 从一组点中找到最大矩形的高效算法

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

是的，有一个 O(n log n) 时间算法(应该与元素差异性下界匹配)。
找到，对于每个 p1 就足够了, p2它具有最大的矩形区域，然后返回整体最大的。这可以表示为一个 3D 极值点问题:每个 p2产生 3D 点 (p2[0], p2[1], p2[0] p2[1]) , 和每个 p1产生 3D 矢量 (-p1[0], -p1[1], 1) ，我们想要最大化点积(技术上加上 p1[0] p1[1] ，但这个常数偏移量不会影响答案)。然后我们“只是”必须遵循柯克帕特里克 1983 年的构造。