查找三角形最大可能区域的最快方法

Question

假设我们在平面中有一组点，每个点都由一对整数坐标描述。有没有办法在这个点上找到具有顶点的三角形，并且最大可能区域比O（n^3）算法更快？

Answer 1

1. 找到凸包。
2. 对于位于凸包上的点（A，B）的每个对，找到第三点C，给出三角形ABC的最大面积。这可以使用O（log n）中的二进制搜索完成。

要进行二分搜索，请按照某种顺序（例如逆时针）排列凸包上的点。 A和B之间有两个点序列，一个从A到B，另一个从B到A.分别考虑每个点。

二分查找步骤如下。在点间隔的中间连续三点C，C'，C“。计算CAB，C'AB，C''AB三个区域。如果C'是三者中最大的，那么它是全球最大值，搜索结束。如果C最大，则最大值在间隔的左半部分。如果C'最大，则最大值在右半部分。 （编辑：注意，新的时间间隔应该在其中一端包含C'）。

那里，一个算法在O（n^2 log n）中工作。

编辑2：this question的答案显示了如何更快地做到这一点。你可以将两种方法结合起来做更好的事情（在O（log n））中，在构造凸包之后，尽管它的构造仍然是O（n log n））。