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/

相关文章:

c# - 在 .NET CF 中预处理和搜索文本文件的最佳方式

c - 与 Ubuntu 相比,我的 C 代码在 Mac 中运行缓慢

c++ - 使用 CGAL : extract only edge points (convex hull) 的 Voronoi 图

预算内最高值(value)的算法

algorithm - 使用哪种算法为学校生成时间表

algorithm - 多维数据分类

javascript - 一次显示页面内容

顺时针排序一组点并确保连接这些点的路径闭合的算法

math - 找到椭圆的所有 4 个可能的法线

c++ - 实现绕组数算法来计算内部和外部区域(OpenGL,c++)