fin*_*nnw 21 compression algorithm geometry closest-points
是否有一种已知的,有效的算法,用于在云中找到最接近的三个点组？
这类似于最接近的一对点问题,但我正在寻找三点而不是两点.
编辑
"最接近"的定义将影响算法的复杂性.正如杰克指出的那样,找到最小面积三角形是3sum-hard,并且在任何情况下都不适合我的应用.
我希望有一个更有效的算法来找到最小的perimiter(即| AB | + | AC | + | BC |)三角形或类似的东西(例如最小| AB |²+ | AC |²+ | BC |².我知道没有理由为什么这应该是3sum-hard,因为其他地方存在3个共线点不会影响结果.
注意:我的点有八个维度,因此任何限制为较少维度的算法都不合适.
该问题类似于在一组点中找到最接近的对的经典问题.您可以调整解决最近对问题的最坏情况O(n log n)算法来解决这个问题.
具体问题出现在Google的Code Jam竞赛中.这是分析的简历:
点数可能非常大,因此我们需要一种有效的算法.我们可以使用分而治之来解决O(n log n)时间内的问题.我们将通过垂直线将点集分成两组相等的大小.现在有三种最小周长三角形:它的三个点可以完全在左侧,完全在右侧,也可以使用每个半点.
进一步:
"要找到第三种情况的最小周长(如果它小于p)":
我们可以证明框中的点数最多为16,因此我们每个点只需考虑一个小的恒定数量的三角形.
在我看来,你甚至可以调整方法在| AB |²+ | AC |²+ | BC |²的情况下工作.
有一个明显的算法可以在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 可能可以以某种方式合并）。