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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.