The minimal spanning tree problem of a point set in a k-dimensional
Euclidean space is considered and a new version of the multifragment
MST-algorithm of Bentley and Friedman is given. The minimal spanning
tree is found by repeatedly joining the minimal subtree with the
closest subtree. A k-d tree is used for choosing the connecting
edges. Computation time of the algorithm depends on the configuration
of the point set: for normally distributed random points the algorithm
is very fast. Two extreme cases demanding O(n log n) and O(n^{2})
operations, n being the cardinality of the point set, are also given

@article{NEK1981J,
author = {O. Nevalainen and J. Ernvall and J. Katajainen},
title = {Finding minimal spanning trees in a {E}uclidean coordinate space},
journaltitle = {BIT},
volume = {21},
number = {1},
year = {1981},
pages = {46--54},
}