5
$\begingroup$

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
Improve this question
$\endgroup$
1
  • $\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
    Commented Apr 25, 2018 at 12:27

1 Answer 1

Reset to default
5
$\begingroup$

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

                    Abstract
                    Fig6a
                    Fig.6a.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .