algorithm - 最大权重欧几里得生成树

Question

通过运行 kruskal 算法可以找到最大生成树（只需更改边函数并首先考虑最大权重边）。我有兴趣找到最大权重欧几里得生成树。是否存在比 kruskal 更好的算法（更好的最坏情况运行时间）来找到这样的生成树？

Answer 1

蒙马等人。O(n log h)在时间和O(n)空间上解决这个问题，其中n是点的数量，h是凸包的大小。

该算法（论文的第 10 页）相当简单，因此即使不了解完整证明也应该可以访问它。