arrays - 找到最大可能三角形面积的最快方法

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：这个问题的答案显示了如何显着更快地做到这一点。您可以将这两种方法结合起来做得更好（在构建凸包后的 O(log n) 中，尽管构建凸包仍然是 O(n log n)）。