凸包中最大的三角形

这个问题已经得到解答，但我面临的主要问题是理解答案之一..

From https://stackoverflow.com/a/1621913/2673063 https://stackoverflow.com/a/1621913/2673063

下面的算法是怎样的O(n) ?

它指出 如果有必要，首先对点进行排序/计算凸包（在 O(n log n) 时间内），我们可以假设我们有凸多边形/凸包，其中的点按照它们在多边形中出现的顺序循环排序。称这些点为 1, 2, 3, … , n。让（变量）点 A、B 和 C 分别从 1、2 和 3 开始（按循环顺序）。我们将移动 A、B、C，直到 ABC 成为面积最大的三角形。 （这个想法类似于计算直径（最远对）时使用的旋转卡尺方法。）

在 A 和 B 固定的情况下，只要三角形的面积增加，即只要满足面积(A,B,C) ≤ 面积(A,B,C+1)。对于固定的 A 和 B，该点 C 将是最大化面积 (ABC) 的点。（换句话说，函数面积 (ABC) 作为 C 的函数是单峰的。）

接下来，如果增加了面积，则推进 B（不改变 A 和 C）。如果是这样，请再次按上述方式推进 C。然后如果可能的话再次推进B，等等。这将给出以A为顶点之一的最大面积三角形。 （到这里的部分应该很容易证明，并且简单地为每个 A 单独执行此操作将给出 O(n2)。但是请继续阅读。）现在再次推进 A，如果它改善了面积等。 虽然这有三个“嵌套”循环，但请注意，B 和 C 总是“向前”前进，并且它们总共最多前进 2n 次（类似地，A 最多前进 n 次），因此整个过程需要 O(n) 时间运行。

作为作者答案 https://stackoverflow.com/a/1621913/4958这就是问题的主题，我觉得有必要更详细地解释一下O(n)运行。

首先，作为一个例子，这是论文中的一张图，显示了针对特定样本输入（12 边形）的算法的前几个步骤。首先我们从A、B、C作为三个连续的顶点开始（图中的步骤1），只要面积增加就推进C（步骤2到6），然后推进B，依此类推。

上面带有星号的三角形是“锚定局部最大值”，即对于给定 A 来说最好的三角形（即，前进 C 或 B 会减小面积）。

就运行时而言O(n)：设 B 的“实际”值（以递增次数表示并忽略回绕）为 nB，类似地，C 为 nC。 （换句话说，B = nB % n and C = nC % n.) 现在请注意，

1. （“B 领先于 A”）无论 A 的值是多少，我们都有 A ≤ nB

2. nB一直在增加

因此，当 A 从 0 到 n 变化时，我们知道 nB 仅在 0 到 2n 之间变化：它最多可以递增 2n 次。类似地，nC。这表明算法的运行时间与 A、B 和 C 递增的总次数成正比，受 O(n) + O(2n) + O(2n) 限制，即 O(n ）。