# Finding Euclidean Minimum Spanning Tree

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?

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:
• WSPD based approaches (first find clusters on Quadtree of $$P$$, then build MSTs for each cluster and then connect clusters to get complete MST)