22

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

这类似于最近的一对点问题，但我正在寻找三个点而不是两个点。

编辑
“最接近”的定义会影响算法的复杂性。正如杰克指出的那样，找到最小面积三角形是 3sum-hard 并且无论如何都不太适合我的应用程序。

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

注意：我的点有八个维度，所以任何限制在较少维度的算法都不适合。

4

4 回答 4

7

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

具体问题在 Google 的 Code Jam 竞赛中有所体现。以下是分析的简历：

点的数量可能非常大，因此我们需要一个有效的算法。我们可以使用分治法在O(n log n)时间内解决问题。我们将通过一条垂直线将一组点分成大小相等的两组。最小周长三角形现在有三种情况：它的三个点可以完全在左侧集合中，完全在右侧集合中，或者它可以使用每一半的点。

更远：

“找到第三种情况的最小周长（如果它小于 p）”：

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

我们可以证明，盒子中的点数最多为 16 个，因此我们只需要为每个点考虑最多一个小的常数三角形。

在我看来，您甚至可以调整该方法以适用于 |AB|²+|AC|²+|BC|² 的情况。

于 2011-09-30T09:28:53.960 回答
5

有一个明显的算法适用于O(n^2).

1）执行Delaunay三角剖分- O(n log n)，所以我们得到一个平面图。

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

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

步骤 2) 需要多长时间？由于图形是平面的，所以边数 <= 3n - 6，即O(n). 所以这一步将O(n^2)在最坏的情况下进行（O(n)在典型情况下，每个顶点的度数是有限的）。

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

于 2011-09-30T14:51:17.550 回答
1

您提到的问题是 3sum 难题的变体。详情请查看http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf。

这个问题也可以表示为从给定点找到最小的三角形。

编辑：

本质上，3sum 难题意味着下限是 O(n^2)。这里和那里可能会有一些小的改进，但没有什么可以做的。

对于这个特定问题（最小三角形），请参阅http://www.cs.princeton.edu/~chazelle/pubs/PowerDuality.pdf的第 3 章。

于 2011-09-24T16:13:54.493 回答
1

这是k-最近邻问题的一种特殊形式，即k=3。引用的页面没有指定算法的复杂性，但很明显可以看到计算从选定点到所有其他点的距离的天真方法，然后计算从该点到所有其他点的距离，以及距离我们的原始点到新选择的点是 O(n k-1 )。考虑伪代码：

for pointB in searchSpace do:
    distanceAB := calculateDistance(pointA, pointB)
    for pointC in {searchSpace} - {pointB} do:
        distanceBC := calculateDistance(pointB, pointC)
        distanceCA := calculateDistance(pointC, pointA)
        if (distanceAB + distanceBC + distanceCA) < currentMin then:
            currentMin := distanceAB + distanceBC + distanceCA
            closestPoints := {pointA, pointB, pointC}

请注意，我们假设pointA已经从searchSpace. 这是一个 O(n 2 ) 算法。假设维度相对较小，或者函数calculateDistance随维度线性增长或更小，这会在适当的时间约束内给出解决方案。当然可以进行优化，但可能不需要。

如果你想看一些真实的代码，维基百科有很多实现 的链接。

于 2011-09-29T18:55:29.113 回答