使用Delaunay Triangulation加速Python MST计算

Question

我有一个代码可以让许多点的最小生成树（大约25000个数据集在每个集合中包含40-10000个点），这显然需要一段时间。我正在使用scipy.sparse.csgraph中的MST算法。

我被告知MST是Delaunay Triangulation的一个子集，所以有人建议我通过先找到DT并从中找到MST来加速我的代码。

有谁知道这会造成多少差异？另外，如果这使得它更快，为什么它不是算法的一部分？如果计算DT然后计算MST更快，那么为什么scipy.sparse.csgraph.minimum_spanning_tree会做其他的事情呢？

请注意：我不是计算机专家，有些人可能会说我应该使用不同的语言，但是Python是我所知道的唯一一个可以做这种事情的人，并且请在您的答案中使用简单的语言，请不要使用行话！

Answer 1

注：这是假定我们在2-d

我怀疑你现在正在做的是喂养所有点对点距离的MST图书馆工作。这些距离有N^2的数量级，并且Kruskal算法在这样的输入上的渐近运行时间是N^2 * logN。

用于Delaunay三角测量的大多数算法花费NlogN时间。一旦三角测量已经计算出来，只需要考虑三角测量中的边缘（因为MST总是三角测量的一个子集）。有O（N）这样的边缘，所以在scipy.sparse.csgraph中Kruskal算法的运行时间应该是N log N.所以这会带来N log N的渐近时间复杂度。

scipy.sparse .csgraph不包含Delaunay三角剖分，该算法适用于任意输入，而不仅仅是欧几里得输入。

我不太确定这对你有多大的帮助，但看起来像是渐进的。