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?
