graph-algorithm - 没有三角剖分的欧几里得最小生成树

Question

我正在浏览一些关于使用 Delaunay 三角测量技术找到 EMST（欧几里得 MST）的文本，但也在某处读到可以通过扫描线算法找到 EMST。由于这更容易实现，我想实现它而不是使用现有的库。任何人都可以指导我/指导我到一个（可能是免费的）论文/资源的链接，该论文/资源解释了这个算法吗？

Answer 1

从这个和摘要来看，这个和这个应该让你开始。他们都使用扫描线算法来获得 MST

Answer 2

I think the simplest technique for finding Euclidean minimum spanning tree is Delaunay trinangulation, use Bowyer-Watson algorithm. It is very easy to implement, once you have that, you can just use something like Kruskal's algorithm, using the distance as the edge weight.