Finding Euclidean Minimum Spanning Tree

Question

Given a set of point $P$. Find the euclidean minimum spanning tree where each points is equally distributed on the plane using randomization.

We can solve this problem with Prim's algorithm in $O(n^2)$ which is too slow. I've found an algorithm called Delanuay Triangulation but is there any other ways to solve this problem in $O(n log n)$ or faster?

Answer 1

If you're asking this question because you want something easier to implement than a Delaunay triangulation algorithm you're most likely out of luck.

You should also specify in what space you're operating. If you're working with $\mathbb N^2$ coordinates, you can possibly do it in $\mathcal O(n \log\log n)$ (with a randomized algorithm to generate the triangulation).

If you have $P\in \mathbb R^2$ your choices (ordered by difficulty of implementation from easiest to not-easiest) are:

• Delaunay triangulation
• WSPD based approaches (first find clusters on Quadtree of $P$, then build MSTs for each cluster and then connect clusters to get complete MST)
• Improved version of Boruvka's algorithm: paper

The last one is also an improvement over the other two in higher dimensions. This answer is more or less a condensed version of the literature review of the linked paper.