给定一组点，求最小面积三角形

Question

给定一组n个点，我们能否找到三个点来描述一个最小面积的三角形，时间复杂度为O(n^2)？如果可以，如何实现？如果不行，我们能比O(n^3)更好地解决吗？

我找到了一些论文，它们声称这个问题至少和寻找三个共线点（面积为0的三角形）的问题一样难。这些论文通过将其简化为3-sum问题的一个实例来描述了这个问题的O(n^2)解决方案。然而，我没有找到任何与我感兴趣的内容相关的解决方案。请参见this（查找一般位置）以获取此类论文和有关3-sum的更多信息。

- IVlad

Answer 1

有一些O(n²)算法可以用于查找最小面积三角形。

例如，您可以在此处找到其中一个：http://www.cs.tufts.edu/comp/163/fall09/CG-lecture9-LA.pdf

如果我正确理解了那个pdf，基本思想如下：

1. 对于每对点AB，找到距离它最近的点。

2. 构造点的对偶，使线 <-> 点。线y = mx + c被映射到点(m,c)

3. 在对偶中，对于给定的点（它对应于原始点集中的线段），垂直的最近线条为我们提供了1所需的点。

显然，2和3可以在O(n²)时间内完成。

此外，我怀疑这些论文通过将问题归约到3SUM来显示3SUM难度。应该反过来。

- Aryabhatta

---

我链接的那篇论文似乎可以简化为3-sum问题。他们将问题简化为寻找三个值a b c，使得a + b + c = 0。+1，需要仔细阅读才能理解。如果没有更好的解决方案，稍后我会接受这个答案。 - IVlad

我知道这是一个旧帖子，但我有两个问题：1）如果我们知道顶点来自（1000,1000）网格，我们能否做得更好？2）如果问题改为查找凸多边形的最小面积（给定n），那么渐近极限将是什么？ - Naman

Answer 2

有一种算法可以在O(n^2*log(n))的复杂度下找到所需的面积。

对于集合中的每个点Pi，请执行以下操作（不失一般性，我们可以假设Pi在原点或将点平移使其如此）。

然后，对于每个点(x1,y1),(x2,y2)，三角形面积将是0.5*|x1*y2-x2*y1|，因此我们需要最小化该值。我们不必遍历所有剩余点的配对（这会给我们O(N^3)的复杂度），而是使用谓词X1 * Y2 < X2 * Y1对这些点进行排序。据称，要找到最小面积的三角形，我们只需要检查排序数组中相邻点的配对。

因此，每个点的此过程的复杂度为n*log(n)，整个算法的复杂度为O(n^2*log(n))。

附注：无法快速找到证明此算法正确的证明:(，希望稍后能找到并发布。

- Vladimir

---

你能详细解释一下吗？为什么三角形的面积是 0.5|x1*y2 - x2*y1|？这似乎是一个行列式，但它只使用了两个点，无法得出三角形面积。此外，为什么在每个点上进行排序时，每次排序看起来都是相同的？最后，你的算法似乎没有包括 Pi，每个 Pi 扮演的角色是什么？ - IVlad

@IVlad 我认为，对于每个点PI，他将每个点(x, y)转换为(x - PI.x, y - PI.y)。（因此，将PI本身移动到坐标原点）算法看起来是可行的。 - Nikita Rybak

再仔细看，有一个问题。假设 PI 是 (0, 0)，还有另外三个点：A(100, 100)，B(2, 1)，C(1, 2)。很明显应该使用点 B 和 C，但排序后的顺序应为 B、A、C。 - Nikita Rybak

@IVlad 不是的。我的最初印象是算法试图为每个给定的 PI 找到最优解（直到我仔细看它）。如果不是这样，证明就更加必要了。 - Nikita Rybak

@IVlad 虽然我认为我们可以扩展上一个例子。想象一个小的完美三角形在一个大的完美三角形内部。（或者你可以取一个完美形状的六边形，将其中一个基本三角形增加而不移动它。）然后对于小三角形的每个顶点，我们都得到了上述情况。 - Nikita Rybak

Answer 3

这个问题

给定一个有n个点的集合，我们能否在O(n^2)的时间内找到三个点，这三个点可以描述出最小面积的三角形？如果可以，如何实现？如果不行，我们能否做得比O(n^3)更好？

这个问题最好在James King, A Survey of 3sum-Hard Problems, 2004这篇论文中解决。

- Pablo