寻找三角形最大可能面积的最快方法

Question

4

假设我们在平面上有一组点，每个点由一对整数坐标描述。有没有一种方法可以更快地找到以这些点为顶点的三角形，使其面积最大，而不是使用O(n^3)的算法。

- Macaronnos

1

http://math.stackexchange.com/ 是一个很好的地方来提问这个问题。 - O. Jones

2

你也可以尝试访问以下网站：http://cs.stackexchange.com/ - jfs

1

@OllieJones 我怀疑不是这样的 - 这是一个算法（即编程）问题。 - Bernhard Barker

1

一种优化方法是找到所有点的凸包。这样可以消除位于凸包内部的点。 - Abhishek Bansal

凸包算法 - Gabriel L.

2

相关：https://dev59.com/13I-5IYBdhLWcg3w487k - Vaughn Cato

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- n. m. · Accepted Answer

要进行二分查找，请按某种顺序（例如逆时针）排列凸包上的点。在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)）。