Efficient minimal spanning tree in metric space

Question

I have a large set of points (n > 10000 in number) in some metric space (e.g. equipped with Jaccard Distance). I want to connect them with a minimal spanning tree, using the metric as the weight on the edges.

• Is there an algorithm that runs in less than O(n²) time?
• If not, is there an algorithm that runs in less than O(n²) average time (possibly using randomization)?
• If not, is there an algorithm that runs in less than O(n²) time and gives a good approximation of the minimum spanning tree?
• If not, is there a reason why such algorithm can't exist?

Thank you in advance!

Edit for the posters below: Classical algorithms for finding minimal spanning tree don't work here. They have an E factor in their running time, but in my case E = n² since I actually consider the complete graph. I also don't have enough memory to store all the >49995000 possible edges.

Answer 1

Apparently, according to this: Estimating the weight of metric minimum spanning trees in sublinear time there is no deterministic o(n^2) (note: smallOh, which is probably what you meant by less than O(n^2), I suppose) algorithm. That paper also gives a sub-linear randomized algorithm for the metric minimum weight spanning tree.

Also look at this paper: An optimal minimum spanning tree algorithm which gives an optimal algorithm. The paper also claims that the complexity of the optimal algorithm is not yet known!

The references in the first paper should be helpful and that paper is probably the most relevant to your question.

Hope that helps.