是否有一种已知的、有效的算法来查找最接近的组three云中的点？
这类似于最近点对问题 http://en.wikipedia.org/wiki/Closest_pair_of_points_problem但我正在寻找三点而不是两点。
Edit
“最接近”的定义会影响算法的复杂度。作为Jack https://stackoverflow.com/questions/7539623/closest-group-of-3-points/7540179#7540179指出，找到最小值area三角形是 3sum-hard 的，无论如何都不太适合我的应用程序。
我希望有一个更有效的算法来找到最小值周长（即|AB|+|AC|+|BC|）三角形或类似的东西（例如最小|AB|²+|AC|²+|BC|²。）我不知道为什么这应该是3sum-hard，因为其他地方存在 3 个共线点不会影响结果。
注意：我的点有八个维度，因此任何仅限于更少维度的算法都不适合。
这个问题类似于在一组点中寻找最接近的点对的经典问题。你可以适应最坏的情况O(n log n)解决最近对问题的算法来解决这个问题。
这个具体问题在 Google 的 Code Jam 竞赛中得到了重点关注。
以下是分析的简历：
点数可能非常大，因此我们需要一种有效的算法。我们可以解决这个问题O(n log n)时间使用分而治之。我们将通过一条垂直线将点集分成大小相等的两组。现在最小周长三角形有三种情况：它的三个点可以完全在左集中，完全在右集中，或者可以使用每一半的点。
Further:
“求第三种情况的最小周长（如果小于 p）”：
- 我们选择距垂直分隔线 p/2 距离内的点。
- 然后我们从上到下迭代这些点，并维护一个大小为 p x p/2 的框中所有点的列表，框的底部边缘位于最近考虑的点。
- 当我们将每个点添加到框中时，我们使用该点和框中的每对点来计算所有三角形的周长。 （我们可以完全排除分界线左侧或右侧的三角形，因为这些已经被考虑在内。）
我们可以证明盒子里的点的数量最多是16个，所以我们只需要考虑每个点最多有一个小的常数个三角形。
在我看来，您甚至可以调整该方法以在 |AB|²+|AC|²+|BC|² 情况下工作。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
