Creating a "satisfactory" Minimum Spanning Tree (MST) given only vertices

Question

Classic MST Problems

In the classic formulation of the Minimum Spanning Tree (MST) problem, we are given a set V of vertices and a set E of edges. Although there are

possible edges given V vertices, the number of edges is usually much smaller than M.

My Problem: Set of edges is implied, not given

In my case I have a set of V vertices, where each vertex is a coordinate (x,y) on a 2-D plane. I am not given any edges at all, i.e., the set E is empty. In actual fact, I know all M edges and their distances: it is the distance between every possible pair of vertices. Thus, the size of the known edges is maximal, i.e., |E|=M.

Here's my dilemma: if the size of V, |V|, is very large (e.g., 10,000), the value of M grows very quickly. Attempting to use an MST algorithm with |V| = 10,000 and |E| = M = 50,000,000 can cause serious algorithmic efficiency issues.

Is there a method for removing / pruning / removing edges from the maximal edge set E before running the MST algorithm, reducing the time needed to find a "satisfactory" (i.e., not necessarily optimal) MST?

Possible Heuristic

Here's one possibility:

• Given the set V of vertices, compute the bounding rectangle
• Partition the rectangle into R smaller rectangles
  • For example, divide the rectangle both vertically and horizontally into four (4) ranges, producing sixteen (16) smaller rectangles
• For each sub-rectangle, compute an MST from all vertices located in the sub-rectangle.
• Connect the resulting MSTs to produce one large MST.

Can anyone suggest an efficient algorithm to generate a satisfactory MST given only the set of vertices?

Answer 1

It sounds like you are trying to compute a Euclidean minimum spanning tree.

Wikipedia contains more efficient O(nlogn) algorithms for this based on the key idea:

A better approach to finding the EMST in a plane is to note that it is a subgraph of every Delaunay triangulation of the n points, a much-reduced set of edges: