Max weight euclidean spanning tree

Question

A maximum spanning tree can be found by running kruskal's algorithm(just changing the edges function and considering the max weight edges first). I am interested in finding the max weight euclidean spanning tree. Does there exist a better algorithm(better worst case running time) than kruskal's to find such a spanning tree?

Answer 1

Monma et al. solve this in O(n log h) time and O(n) space, where n is the number of points and h is the size of the convex hull.

The algorithm (p.10 of the paper) is fairly simple so it should be accessible even without understanding the full proof.