Do I need a delauny triangulation to find the minimum spanning tree?

Question

I understand that the MST is a subset of the delauny triangulation but how can it help to find a minimum spanning tree? What is the meaning when I use an edge of a delauny triangulation for the MST? How is this different from not triangulate a set of points before finding a MST?

Answer 1

the standard mst algorithms operate on an graph. if you start with a set of vertices without any other information but the pairwise (abstract) distances between the vertices, your standard approach would require you to run a mst algorithm on the complete graph with O(n^2) edges. as the complexity of the standard mst algorithms depend on the number of edges (eg. O(e log e) for Kruskal), it would be more efficient if you could curtail the number of edges in the graph to start with - which applies to the delaunay triangulation regarded as a graph since it sports O(n) edges (i will not discuss that there is a mst of the original point set being a subset of the delaunay graph, as you acknowledge that).

your original point set might be subject to other constraints that either prevent a delaunay triangulation (eg. collinear points) or allow for a even sparser graph to start with ( eg. a convex hull with a minimum diameter less than the minimum distance between two points in your point set ).

regards, carsten