There are several O(n log n) algorithms to construct the minimum spanning tree of n points in the plane. For instance, one may construct the Voronoi diagram (or its dual, the Delauney triangulation) of the n points in time O(n log n) by the divide-and-conquer algorithm of Shamos, and then use the observation, also due to Shamos, that the minimum spanning tree is a subgraph of the Delauney triangulation. Since the Delauney triangulation is a planar graph, this step can be done in time O(n).

The authors simplify this process by modifying the divide-and-conquer algorithm to compute directly the minimum spanning tree rather than the whole Delauney triangulation. The modification appears straightforward, and the algorithm is simple and appealing. A parallel implementation with O(log n) processors and worst-case time O(n) is also described. For more recent development on minimum spanning tree algorithms in general, see [1].