Computing Euclidean maximum spanning trees
Clyde L. Monma, Mike Paterson, Subhash Suri, Fei Yao · 1988
An algorithm is presented for finding a maximum-weight spanning tree of a set of n points in the Euclidean plane, where the weight of an edge (pi, pj) equals the Euclidean distance between the points pi and pj. The algorithm runs in time Ο (n logn) and requires Ο (n) space. If the points are vertices of a convex polygon (given in order along the boundary), then our algorithm requires only a linear amount of time and space. These bounds are the best possible in the algebraic computation-tree model. We also establish various properties of maximum spanning trees that can be exploited to solve other geometric problems.