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.

Could someone point me to the right references about this problem from which I could:

  1. Learn theory behind
  2. Write exact algorithm to solve this problem
  • $\begingroup$ 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)$. $\endgroup$ – 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."

Arya, Sunil, and David M. Mount. "A fast and simple algorithm for computing approximate Euclidean minimum spanning trees." Proceedings 27th Annual ACM-SIAM Symposium Discrete Algorithms. SIAM, 2016. (PDF download.)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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