# Minimum euclidean spanning tree in n dimensional space

I need to compute the minimum euclidean spanning tree in $R^d$ and do it with some algorithm that can do it with complexity near to $\Omega(nlogn)$ where $n$ is the size of the point set.

Right now I'm thinking about usage of delaunay triangulation for my set of points and after that use some MST algorithms like Prim\Kruskal, but as far as I see this won't give me needed complexity bounds.

1. Learn theory behind
2. Write exact algorithm to solve this problem
• I think you mean $O(n \log n)$ rather than $\Omega(n \log n)$: the latter is a lowerbound, but you seek an algorithm no worse than the upperbound $O(n \log n)$. – Joseph O'Rourke Apr 25 '18 at 12:27

The best you can hope for is $O(n \log n)$ plus a term dependent upon accuracy, for finding an approximate Euclidean MST. The fastest known exact algorithm is just a hair better than quadratic, $O(n^2)$. Below is a central paper on the topic. Note especially: "The algorithm is deterministic and very simple."