不带三角剖分的欧式最小生成树 [英] Euclidean Minimum Spanning Tree Without Triangulation

问题描述

我一直在浏览有关使用Delaunay三角剖分技术找到EMST(Euclidean MST)的文章，但同时也读到可以通过扫掠线算法找到EMST的地方.因为这样做会更容易实现，所以我想实现它而不是使用现有的库. 任何人都可以引导我/将我定向到具有该算法说明的(可能是免费的)论文/资源的链接吗?

I was looking through some text about finding the EMST (Euclidean MST) using Delaunay triangulation technique, but also read somewhere that the EMST can be found through a sweep line algorithm. Since this would easier implementing, I would like to implement this rather than using a existing library. Can anyone guide me/ direct me to a link to a (possibly free) paper/source that has this algorithm explained?

推荐答案

来自此应该可以帮助您入门.他们都使用扫掠线算法来获取MST.

From this and going by the abstracts, this and this should get you started. They both use sweepline algorithms to obtain MST's

这篇关于不带三角剖分的欧式最小生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！