Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
We have an unstructured cloud of $N$ points in 3D space. What is known about the complexity of building the Euclidean Minimum Spanning Tree of the points ?
The tree is made of $N-1$ edges and can be built as a subset of the Delaunay triangulation in time $O(N^2)$, but I don't think that this is tight.
The current Wikipedia article has information:
For three dimensions it is possible to find the minimum spanning tree in time $O((n \log n)^{4/3})$
And about approximation:
it is possible to produce a $(1 + \varepsilon)$-approximation in $O(n \log n)$ time, whenever $\varepsilon$ is a constant.
In practice, worst-case quadratic algorithms are used because worst-case inputs are rare and fast enough most of the time.
