可能重复：
除了蛮力搜索之外，如何在凸包中找到最大的三角形
我有一组随机点，我想从中找到按面积计算的最大三角形，每个顶点都在其中一个点上。
到目前为止，我已经发现最大三角形的顶点只会位于点云（或凸包）的外部点上，所以我编写了一个函数来做到这一点（在 nlogn 时间内使用 Graham 扫描）。
然而，这就是我卡住的地方。我可以弄清楚如何从这些点中找到最大三角形的唯一方法是在 n^3 时间使用蛮力，这在平均情况下仍然是可以接受的，因为凸包算法通常会剔除绝大多数点。然而，在点在一个圆上的最坏情况下，这种方法将失败。
有人知道更有效地做到这一点的算法吗？
注意：我知道 CGAL 有这个算法，但他们没有详细说明它是如何完成的。我不想使用库，我想学习这个并自己编程（并且还允许我将它调整到我想要它的操作方式，就像其他实现拾取共线点的格雷厄姆扫描一样我不想）。
不知道这是否有帮助，但是如果您从凸包中选择两个点并旋转该包的所有点，使两个点的连接线平行于 x 轴，要么是最大值的点，要么是具有最小 y 坐标的一个与首先选择的两个点一起形成面积最大的三角形。
当然，一旦您针对所有可能的基线测试了一个点，您就可以将其从列表中删除。
在我的脑海中，也许你可以做一些涉及网格化/将点集合分成组的事情？也许......将点分成三组（但不确定在这种情况下最好的方法是什么），做一些事情来丢弃每组中比其他点更接近其他两组的点同一组，然后使用剩余的点找到可以在每个组中具有一个顶点的最大三角形？这实际上会使所有点都在一个圆上的情况变得更加简单，因为您只需关注每个组中包含的弧中心附近的点，因为这些点将是每个组中最远的点另外两组。
不过，我不确定这是否会为您提供某些三角形/点分布的正确结果。可能存在结果三角形不是最佳区域的情况，因为分组和/或顶点选择不是/不是最佳的。类似的东西。
无论如何，这些是我对这个问题的看法。我希望我至少能够为您提供有关如何处理它的想法。
这是关于如何将其降低到 O(n 2 log n) 的想法。我对计算几何一无所知，所以我将其标记为社区 wiki；请随时对此进行改进。
通过为每个点找到通过该点的线的斜率范围来预处理凸包，使得集合完全位于线的一侧。然后反转这种关系：为具有叶节点中的点的斜率构造一个区间树，这样当使用斜率查询时，您会找到通过这些点有切线的点。
如果凸包上没有三个或更多共线点的集合，则每个斜率最多有四个点（每边两个），但在共线点的情况下，我们可以忽略中间点。
现在，遍历凸包上的所有点对 (P,Q)。我们想找到点 R 使得三角形 PQR 的面积最大。以 PQ 作为三角形的底，我们希望通过找到 R 尽可能远离线 PQ 来最大化高度。通过 R 平行于 PQ 的线必须使所有点都位于线的一侧，因此我们可以使用预先构建的区间树在时间 O(log n) 内找到有限数量的候选。
为了在实践中进一步改进这一点，在点对集合中进行分支定界：找到任何三角形高度的上限（例如两点之间的最大距离），并丢弃距离相乘的任何点对这个上限小于迄今为止发现的最大三角形。
我认为旋转卡尺方法可能适用于此。
从凸包中一次删除一个点怎么样？从凸包开始，计算每个三元组相邻点（p1p2p3、p2p3p4 等）形成的三角形的面积。找到面积最小的三角形，然后放下形成该三角形的三个点的中间。（换句话说，如果面积最小的三角形是 p3p4p5，则删除 P4。）现在您有一个具有 N-1 个点的凸多边形。重复相同的过程，直到剩下三个点。这应该花费 O(N^2) 时间。
如果在某些病理情况下这不起作用，我一点也不感到惊讶，但我希望它适用于大多数情况。（换句话说，我还没有证明这一点，也没有可以引用的来源。）