algorithm - 最近的 3 点组

Question

是否有一种已知的高效算法可以找到云中最近的 三个 点组？

这类似于 closest pair of points problem但我正在寻找三分而不是两分。

---

编辑
“最接近”的定义会影响算法的复杂度。作为Jack指出，找到最小面积三角形是 3sum-hard 并且在任何情况下都不太适合我的应用程序。

我希望有一个更有效的算法来找到最小周长(即|AB|+|AC|+|BC|)三角形或类似的东西(例如最小|AB|²+ |AC|²+|BC|²。)我不知道为什么这应该是 3sum-hard，因为其他地方存在 3 个共线点不会影响结果。

---

注意:我的点有八个维度，因此任何限于较少维度的算法都不适合。

Answer 1

这个问题类似于在一组点中寻找最近对的经典问题。您可以采用解决最接近对问题的最坏情况 O(n log n) 算法来解决这个问题。

Google 的 Code Jam 竞赛中提到了具体问题。 以下是分析的摘要:

The number of points can be pretty large so we need an efficient algorithm. We can solve the problem in O(n log n) time using divide and conquer. We will split the set of points by a vertical line into two sets of equal size. There are now three cases for the minimum-perimeter triangle: its three points can either be entirely in the left set, entirely in the right set, or it can use points from each half.

进一步:

"To find the minimum perimeter for the third case (if it is less than p)":

1. 我们选择距离垂直分隔线 p/2 范围内的点。
2. 然后我们从上到下遍历这些点，并维护一个大小为 p x p/2 的盒子中所有点的列表，盒子的底部边缘是最近考虑的点。
3. 当我们将每个点添加到框中时，我们使用该点和框中的每对点计算所有三角形的周长。 (我们可以完全排除分界线左侧或右侧的三角形，因为这些已经被考虑过了。)

We can prove that the number of points in the box is at most 16, so we only need to consider at most a small constant number of triangles for each point.

在我看来，您甚至可以调整该方法以在 |AB|²+|AC|²+|BC|² 情况下工作。