使用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三角剖分，該算法適用於任意輸入，而不僅僅是歐幾里得輸入。

我不太確定這對你有多大的幫助，但看起來像是漸進的。