最近的一组3个点 [英] Closest group of 3 points

问题描述

是否有已知的高效算法可用于在云中查找最接近的三个点的组？

这类似于closest pair of points problem，但我希望得到三个点，而不是两个点。

---

编辑
"最近"的定义会影响算法的复杂度。正如Jack指出的那样，寻找最小面积三角形非常困难，而且无论如何都不太适合我的应用程序。

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

---

注意：我的点有八个维度，因此任何限制为较少维度的算法都不适用。

推荐答案

有一个明显的算法可以在O(n^2)中运行。

1)执行Delaunay triangluation-O(n log n)，得到平面图。

因为它是最大化最小角度的Delaunay三角剖分，所以很明显最近的3个点必须至少由2条边连接(但它们不一定需要形成三角形！)。否则会有更多更接近的点或更多闭合角度。

2)对于每个点(图形的顶点)，我们检查每对相邻边，并查看由这两条边定义的3个顶点。

步骤2)需要多长时间？由于图形是平面的，number of edges is <= 3n - 6, i.e. O(n)。因此，在最坏的情况下，此步骤将花费O(n^2)(在典型情况下，O(n)，其中每个顶点的阶数是有限的)。

所以整个算法是O(n^2)。请注意，步骤2)在某种程度上是幼稚的(暴力)解决方案，因此我认为还有改进的空间(而且，步骤1和步骤2可能会以某种方式合并)。

这篇关于最近的一组3个点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！