Euclidean Minimum Spanning Tree Without Triangulat

Question

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?

Answer 1

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

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.