给定点集的最小面积三角形
给定一组n个点，我们能否在O(n^2)中找到描述面积最小三角形的三个点？如果是，如何实现？如果不是，我们能做得比 O(n^3) 更好吗？
我发现一些论文指出这个问题至少和要求找到三个共线点（面积为 0 的三角形）的问题一样难。这些论文描述了该问题的 O(n^2) 解决方案，将其简化为 3-sum 问题的一个实例。然而，我找不到任何我感兴趣的解决方案。请参阅此（查找一般立场）这样的论文和更多关于 3-sum 的信息。
Given a set of n points, can we find three points that describe a triangle with minimum area in O(n^2)? If yes, how, and if not, can we do better than O(n^3)?
I have found some papers that state that this problem is at least as hard as the problem that asks to find three collinear points (a triangle with area 0). These papers describe an O(n^2) solution to this problem by reducing it to an instance of the 3-sum problem. I couldn't find any solution for what I'm interested in however. See this (look for General Position) for such a paper and more information on 3-sum.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
寻找最小面积三角形的算法有 O(n2) 种。
例如，您可以在这里找到一个： http:// www.cs.tufts.edu/comp/163/fall09/CG-lecture9-LA.pdf
如果我正确理解了该 pdf，基本思想如下：
对于每对点 AB 您找到最接近它的点。
您构造一个对偶点，以便线 <->点。
线 y = mx + c 映射到点 (m,c)
在对偶中，对于给定点（对应于原始集合中的一个段）点）垂直方向上最近的线为我们提供了 1 所需的点。
显然 2 & 3 可以在 O(n2) 时间内完成。
另外，我怀疑论文通过将减少到 3SUM 来显示 3SUM 硬度。应该是相反的。
There are O(n2) algorithms for finding the minimum area triangle.
For instance you can find one here: http://www.cs.tufts.edu/comp/163/fall09/CG-lecture9-LA.pdf
If I understood that pdf correctly, the basic idea is as follows:
For each pair of points AB you find the point that is closest to it.
You construct a dual of the points so that lines <-> points.
Line y = mx + c is mapped to point (m,c)
In the dual, for a given point (which corresponds to a segment in original set of points) the nearest line vertically gives us the required point for 1.
Apparently 2 & 3 can be done in O(n2) time.
Also I doubt the papers showed 3SUM-hardness by reducing to 3SUM. It should be the other way round.
有一种算法可以找到所需区域，复杂度为 O(n^2*log(n))。
对于集合中的每个点 Pi 执行以下操作（不失一般性，我们可以假设 Pi 位于原点或平移点以使其如此）。
那么对于每个点 (x1,y1), (x2,y2) ，三角形面积将为 0.5*|x1*y2-x2*y1|所以我们需要最小化这个值。我们不是迭代所有剩余点对（这给了我们 O(N^3) 复杂度），而是使用谓词 X1 * Y2
X1 * Y2对这些点进行排序。 X2 * Y1。据称，为了找到面积最小的三角形，我们只需要检查排序数组中的相邻点对。所以这个过程对于每个点的复杂度是 n*log(n) ，整个算法的工作时间为 O(n^2*log(n))
PS 无法快速找到该算法正确的证明:(，希望稍后会找到并发布。
There's an algorithm that finds the required area with complexity O(n^2*log(n)).
For each point Pi in set do the following(without loss of generality we can assume that Pi is in the origin or translate the points to make it so).
Then for each points (x1,y1), (x2,y2) the triangle area will be 0.5*|x1*y2-x2*y1| so we need to minimize that value. Instead of iterating through all pairs of remaining points (which gives us O(N^3) complexity) we sort those points using predicate
X1 * Y2 < X2 * Y1. It is claimed that to find triangle with minimal area we need to check only the pairs of adjacent points in the sorted array.So the complexity of this procedure for each point is n*log(n) and the whole algorithm works in O(n^2*log(n))
P.S. Can't quickly find the proof that this algorithm is correct :(, hope will find it it later and post it then.
问题
吗？这篇论文中已经解决了：James King，3sum-Hard 问题调查，2004 年
The problem
is better resolved in this paper: James King, A Survey of 3sum-Hard Problems, 2004