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

原文 标签 algorithm performance computational-geometry

我有一组点,我的目标是选择两个点,以便最大化由两个点形成的矩形的面积(一个代表左下角,另一个代表右上角)。
我可以通过只做两个 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]),但我不确定如何继续。

最佳答案

是的,有一个 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 年的构造。

关于algorithm - 从一组点中找到最大矩形的高效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69275956/

相关文章:

algorithm - 为什么DFS检查图是否为树的速度不够快

c++ - 浮点除法的软件实现,四舍五入问题

graphics - 将任意 2D 多边形投影到 3D 三角形网格上的最佳方法?

java - 2 Java GeneralPath之间的带状线

arrays - 查找已排序和旋转的数组中的最小元素

java - 尝试运行Tarjan算法的Java实现

r - 为什么 `speedglm`比 `glm`慢?

c++ - 更改为C++时陷入while循环

python - 比python中的嵌套循环更快的搜索方式

c++ - 改进点集的最小距离过滤器